[BAEKJOON:1475] 방 번호

문제

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

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

입력

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

출력

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

해결

한 세트 0 ~ 9, 6과 9는 뒤집어서 사용할 수 있다.

각 자리 숫자의 등장 횟수를 센 뒤 6과 9의 횟수를 합쳐 두 장씩 묶는다. 나머지 숫자와 이 묶음에서 필요한 세트 수의 최댓값을 구한다.

6과 9만 합쳐서 세기

한 세트에는 각 숫자가 하나씩 있지만 6과 9의 카드는 서로 뒤집어 쓸 수 있다. 따라서 다른 숫자 d는 필요한 세트 수가 count[d]이고, 6·9는 합친 사용 횟수를 카드 두 장으로 나누어 올림한 값이다. 최종 답은 이 열 가지 요구량의 최댓값이다.

예를 들어 9999는 9가 네 번 나와 6 카드 두 장과 9 카드 두 장, 즉 두 세트가 필요하다. 666999는 합쳐 여섯 번이므로 세 세트다. 0도 방 번호로 허용되므로 0 카드가 하나 필요하다. 코드가 do ... while을 쓴 이유는 입력이 0이어도 한 자리를 처리하기 위해서다.

숫자 하나를 읽을 때마다 해당 자리의 빈도를 올리고, 마지막에 (count[6]+count[9]+1)/2로 올림 나눗셈을 한다. 현재 코드는 반복문에서 6과 9를 두 번 확인하지만 같은 값을 비교할 뿐 결과는 변하지 않는다. 입력 자릿수를 L이라 하면 O(L) 시간, 길이 10인 배열만 사용하므로 O(1) 공간이다.

방 번호	6·9 합계	다른 숫자의 최대 빈도	필요한 세트
0	0	1	1
9999	4	0	2
1222	0	3	3
666999	6	0	3

6과 9만 세면 1222를 한 세트로 잘못 판단한다. 반대로 모든 숫자를 따로 세면 9999에 네 세트가 필요하다고 잘못 판단한다. 합쳐서 나눈 6·9 요구량과 다른 여덟 숫자의 요구량을 함께 비교해야 한다.

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int t = scan.nextInt();
		int[] nums = new int[10];
		int result = 0;

		do {
			nums[t % 10]++;
		} while((t /= 10) > 0);

		for (int i = 0; i < nums.length; i++) {
			result = (i == 6 || i == 9) ? Math.max(result, (nums[6] + nums[9] + 1) / 2) : Math.max(result, nums[i]);
		}
		System.out.println(result);

		scan.close();
	}
}