[백준/C++] 1475번 방 번호

1475번 방 번호

문제

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

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

입력

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

출력

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

풀이

방 번호 빈도 배열을 만들어 풀었다. 길이가 n인 문자열을 한번만 읽으므로 시간복잡도는 O(n)이다.

1. 방 번호에 등장한 숫자의 개수를 담는 배열을 만든다.
2. 문자열로 방 번호를 입력 받는다.
3. 문자 하나씩 읽으면서 해당 문자가 등장한 빈도를 배열에 업데이트한다.
4. 이 때 배열의 최대값을 갱신한다. 숫자가 6 또는 9일 경우는 제외한다.
5. 배열의 최대값과 6과 9가 필요한 경우와 비교하여 더 큰 값을 출력한다.

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int arr[10] = {}, maxN = 0;
  string s;
  cin >> s;

  for (auto c : s){
    int n = c - '0';
    arr[n]++;

    if (n == 6 || n == 9) continue;
    maxN = max(maxN, arr[n]);
  }
  cout << max(maxN, (arr[6] + arr[9] + 1) / 2);
  return 0;
}