[백준 1475] - 방 번호

 

문제

• 다솜이는 은진이의 옆집에 새로 이사왔다.
  • 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.
• 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다.
  • 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다.
• 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

 

입력

• 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

• 첫째 줄에 필요한 세트의 개수를 출력한다.

 

 

솔루션

• 두 가지 방법으로 풀어봤다. (큰 차이는 없는 것 같다)

1. 0 ~ 9 숫자를 소유하고 있는 상태에서, 숫자를 따라가며 해당 숫자 개수를 하나씩 감소시키면서 진행한다.
   • 시작할 때 먼저 1세트를 가지고 있는다.
   • 그 다음, 해당 숫자 갯수를 하나씩 줄여나가면서 진행한다.
   • 만약 해당 숫자 갯수가 0일 때는 케이스를 나눠야 한다.
     • 해당 숫자가 6이면서 9 갯수가 아직 남아있을 경우
       • 6 숫자는 없고, 9 숫자는 남아있으므로, 9 숫자 개수를 하나 감소시킨다.
     • 해당 숫자가 9면서 6 갯수가 아직 남아있을 경우
       • 9 숫자는 없고, 6 숫자는 남아있으므로, 6 숫자 개수를 하나 감소시킨다.
     • 위 경우가 해당 되지 않으면, 0 ~ 9 세트를 하나 추가한다.
   • 이를 숫자 끝까지 진행한다.
2. 이 방법은 반대로 0 ~ 9 세트 개수를 마지막에 계산하는 방식이다.
   • 먼저 숫자를 처음부터 끝까지 훑는 과정을 진행한다.
     • 여기서 어떤 숫자를 가장 많이 썼는지 확인한다.
   • 숫자 끝까지 탐색한 뒤, 케이스를 두 가지로 나눈다.
     • 가장 많이 사용한 숫자가 6 또는 9라면 이 둘의 개수를 더한 뒤에 2로 나눠준 값이 필요한 0 ~ 9 세트 개수이다.
     • 그 이외의 숫자는 숫자 개수 그대로가 세트 개수가 될 것이다.

 

Code

(1) 현재 소유하고 있는 세트 개수를 하나씩 감소시키는 방식

public int solution(String str) {
    int count = 1;
    int[] arr = new int[10];
    Arrays.fill(arr, 1);
 
    for (int i = 0; i < str.length(); i++) {
        int num = str.charAt(i) - '0';
 
        if (arr[num] == 0) {
            if (num == 6 && arr[9] > 0) {
                arr[9]--;
                continue;
            } else if (num == 9 && arr[6] > 0) {
                arr[6]--;
                continue;
            }
            
            count++;
            for (int j = 0; j < arr.length; j++)
                arr[j]++;
        }
        arr[num]--;
    }
 
    return count;
}

 

(2) 세트 개수를 마지막에 계산하는 방식

public int solution(String str) {
    int[] arr = new int[10];
    int max = 0, minidx = 0;
 
    for (int i = 0; i < str.length(); i++) {
        int temp = ++arr[str.charAt(i) - '0'];
        if (max < temp) {
            max = temp;
            minidx = str.charAt(i) - '0';
        }
    }
    
    if (minidx == 6 || minidx == 9)
        max = (arr[6] + arr[9] + 1) / 2;
 
    return max;
}

 

결과