https://www.acmicpc.net/problem/1475
문제
> 다솜이는 은진이의 옆집에 새로 이사왔다.
> 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.
> 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다.
> 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다.
> 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오.
(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)접근
방 번호를 문자열로 받아서 한 자리 씩 숫자로 변환해 이를 인덱스로하여 값으로 1씩 누적한다.
6과 9는 서로 뒤집어서 쓸 수 있으므로 6과9를 제외한 나머지 숫자들 중 가장 많이 필요한 수, 즉 해당 수를 인덱스로 가지는 값중 젤 큰 값을 찾는다.
예를 들어 인덱스 3번의 값이 4라면 숫자 3을 4개 필요한다는 뜻이다.
이제 6,9제외 가장 많이 필요한 개수를 찾았으므로 그 수의 두 배한 값과 총 필요한 6과 9의 개수의 합을 비교한다.
예를들어 3이 4개 필요하면 어차피 0~9까지가 각각 4개씩 있을것이고 6과 9는 서로 뒤집어 사용하니 6과9는 합쳐서 총 8개까지 가능해지는 것이다.
그래서 8개 보다 작거나 같으면 3이 4개 필요하므로 총 4세트가 필요하고, 8개보다 크면 9개나 10개나 1세트 더 필요하게 되므로 6과 9의 개수의 합 -1 을 2로 나눈 뒤 1을 더해 몇 세트가 필요한지 구할 수 있다.
문제해결
> 숫자별 필요한 개수를 저장하기 위해 정수형 배열 num을 0부터 9까지 크기 10으로 선언한다.
> 번호를 문자열로 입력받으며 각 자리를 정수로 변환해 인덱스로 가지며 수를 누적한다.
> 6과9를 제외하고 모든 숫자 중 가장 많이 필요한 수의 개수를 본다.
> 6과9의 개수를 합한 수가 가장 많이 필요한 수의 개수의 2배 이하면, 이 수를 출력한다.
> 더 크다면 6과9의 합 -1을 2로 나눈뒤 1을 더해 세트의 수를 구한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1475번 방 번호
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int[] num = new int[10];
for(int i = 0; i < s.length(); i++) num[s.charAt(i) - '0']++;
int max = 0;
for(int i = 0; i < num.length; i++) {
if(i == 6 || i == 9) continue;
max = Math.max(max, num[i]);
}
if(max * 2 >= num[6] + num[9]) System.out.print(max);
else System.out.print((num[6] + num[9] - 1) / 2 + 1);
}
}
후기
맵을 사용해서 할까 하다가 최대값을 찾아내는 과정이 배열이 더 빠를것 같아 방향을 틀었다.
