백준 20915 - 숫자 카드 놀이 (자바 - 그리디)

https://www.acmicpc.net/problem/20915

20915번: 숫자 카드 놀이

 

* 문제 요약

Albert 는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지 숫자 하나씩이 적혀있고, 6이나 9가 적힌 카드를 회전할 경우 구분할 수 없다.(즉, 6이 적힌 카드는 회전하면 9로 보이고, 9가 적힌 카드는 회전하면 6으로 보인다.)

Albert 는 최근 두 수의 곱셈에 대해 배운터라 n장의 카드를 모두 이용하여 두 개의 수를 만든 후, 그 수의 곱이 최대가 되도록 하고 싶다.

단, n장의 카드 모두 사용하여야 하며, 각 수는 최소 1장(그리고 최대 n-1장) 의 카드로 구성되어야 한다. 6이나 9가 적힌 카드는 Albert 가 임의로 회전하여 사용할 수 있다.

 

예를 들어 n=8 이고 Albert 가 가진 카드가 [2, 0, 2, 0, 2, 0, 2, 1] 이라 하자. 이 때 8장의 카드를 활용하여 "2200" 과 "2210" 을 만들면 두 수의 곱은 4862000 이 된다. 혹은 "2020" 과 "2021" 을 만들어 곱이 4082420 이 되도록 할 수도 있다.

이 예제에서 Albert 가 만들 수 있는 최대 곱은 4862000 이다.

입력으로 Albert 가 가진 n장의 숫자 카드가 주어졌을 때, 달성 가능한 최대 곱을 구하시오.

 

* 입력

첫 줄에 테스트 케이스의 수 T 가 주어진다.

다음 각 줄에 Albert 가 가진 숫자 카드를 표현하는 문자열이 (공백없이) 주어지는데, 문자열의 각 문자는 '0' - '9' 중 하나이다.

 

* 출력

각 테스트 케이스에 대해 Albert 가 만들 수 있는 최대 곱을 출력한다.

 

* 제한

- 1 <= T <= 10

- 2 <= n <= 18

- 모든 입력에 대해 정답은 항상 10^18 이하인 입력만 주어진다.

 

* 예시

 

* 해결 과정

숫자 두 개를 만들어 곱해서 얻을 수 있는 최대값을 구해야 하므로 우선 입력으로 들어온 숫자들 중에서 6이 있으면 확정적으로 9로 바꿔준 후 시작한다.

그 후 입력받은 숫자들을 int 형으로 변환하여 배열에 저장한 다음 만들 수 있는 2가지 숫자의 크기를 최대한 높이기 위해 내림차순으로 배열을 정렬해준 이후 이 숫자들을 순서대로 다시 문자열로 변환하여 붙여준다.

 

그 이후엔 내림차순 정렬을 통해 만들어진 숫자 문자열을 순서대로 하나씩 떼어내가며 두 개의 숫자를 만들때 다음과 같은 로직을 수행한다.

1. 두 개의 숫자 문자열을 각 sb1, sb2 로 지정해준다.

2. sb1 의 길이가 0일 경우 현재 탐색중인 숫자를 sb1 에 붙여준다.

3. sb2 의 길이가 0일 경우 현재 탐색중인 숫자를 sb2 에 붙여준다.

4. 만약 2,3 에 해당되지 않을 경우 sb1, sb2 둘을 비교하여 더 작은 숫자에 현재 탐색중인 숫자를 붙여줘가면서 두 개의 숫자를 완성한다.

5. 반복문이 끝나고 나면 만들어진 2개의 숫자를 곱한 결과를 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());

        for (int i = 0; i < tc; i++) {
            StringBuilder sb = new StringBuilder(br.readLine());

            for (int j = 0; j < sb.length(); j++) {
                if (sb.charAt(j) == '6') {
                    sb.setCharAt(j, '9');
                }
            }

            Integer[] array = new Integer[sb.length()];
            for (int j = 0; j < array.length; j++) {
                array[j] = Integer.parseInt(String.valueOf(sb.charAt(j)));
            }

            Arrays.sort(array, Collections.reverseOrder());
            sb.setLength(0);

            for (int j = 0; j < array.length; j++) {
                sb.append(String.valueOf(array[j]));
            }

            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();

            for (int j = 0; j < sb.length(); j++) {
                if (sb1.length() == 0) {
                    sb1.append(sb.charAt(j));
                } else if (sb2.length() == 0) {
                    sb2.append(sb.charAt(j));
                } else {
                    BigInteger number1 = new BigInteger(sb1.toString());
                    BigInteger number2 = new BigInteger(sb2.toString());

                    if (number1.compareTo(number2) == -1 || number1.compareTo(number2) == 0) {
                        sb1.append(sb.charAt(j));
                    } else {
                        sb2.append(sb.charAt(j));
                    }
                }
            }

            BigInteger result = new BigInteger(sb1.toString()).multiply(new BigInteger(sb2.toString()));
            bw.write(result + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 두 개의 숫자 문자열의 상태를 기준으로 현재 탐색중인 숫자를 어느 문자열에 붙여줄지 결정한다.

선택된 해답이 조건을 만족하는지 검사한다. -> 입력받은 숫자들을 모두 탐색할 때까지 두 숫자의 곱의 최대값을 알 수 없으므로 반복문을 끝까지 수행해준다.

 

위의 과정을 통해 문제를 풀었으므로 그리디 알고리즘에 해당된다.