BOJ 1475 - 방 번호

문제 링크

문제#

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

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

입력#

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

출력#

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

풀이#

방 번호를 만들기 위해 0부터 9까지 숫자 카드가 몇 장 필요한지 세면 되지만, 6과 9는 서로 뒤집어 쓸 수 있다는 점이 핵심이다. 그래서 6과 9는 따로 최대를 보지 않고 둘의 개수를 합쳐 2로 나눈 뒤 올림한 값을 필요한 세트 수로 본다.

코드는 각 자리 숫자의 빈도를 센 뒤, 다른 숫자들의 최댓값과 ceil((cnt[6] + cnt[9]) / 2)를 비교해 답을 구한다. 결국 가장 많이 필요한 숫자가 세트 개수를 결정한다.

코드#

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string s;
int arr[10];
 
int solve() {	
	for (char c : s)
		arr[c - '0']++;
	
	int mid = (arr[6] + arr[9] + 1) / 2;
	arr[6] = arr[9] = mid;
 
	int ans = 0;
	for (int i = 0; i < 10; i++) 
		ans = max(ans, arr[i]);
 
	return ans;
}
 
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> s;
	
	cout << solve() << '\n';
	return 0;
}

복잡도#

• 시간 복잡도: 방 번호의 각 자릿수를 한 번씩 세므로 자릿수를 $D$라 할 때 $O(D)$이다.
• 공간 복잡도: 숫자 카운트 배열 크기가 고정이므로 $O(1)$이다.

마무리#

방 번호를 만들기 위해 0부터 9까지 숫자 카드가 몇 장 필요한지 세면 되지만, 6과 9는 서로 뒤집어 쓸 수 있다는 점이 핵심이다.