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

방 번호

문제 링크

방 번호

분석

번호가 있는 플라스틱 숫자 세트 1개에 0부터 9까지의 수가 하나씩 있을 때, 방 번호를 플라스틱 숫자로 만들려고 할 때 필요한 세트의 수를 구해야합니다.

1개 세트에는 6과 9가 1개씩 들어있지만, 서로 대체할 수 있기 때문에 6과 9를 합친 값에 2를 나누고 올림하여 필요한 최소 개수를 구해야합니다.

풀이

#include <iostream>

int main()
{
    int n;

    std::cin >> n;

    // 0부터 9까지 각 숫자의 등장 횟수를 관리
    int NumCounts[10] = { 0 };

    // 각 자릿수를 분해하여 숫자가 등장하는 횟수를 카운트
    while (n != 0)
    {
        int TargetIndex = n % 10;

        ++NumCounts[TargetIndex];

        n /= 10;
    }

    // 6과 9는 뒤집어서 사용할 수 있으므로 합쳐서 관리
    int FlipCount = NumCounts[9] + NumCounts[6];

    // 6 + 9의 개수를 절반으로 나눈 뒤 올림하여 필요한 개수를 구한다.
    // 6에는 올림 효과를 준다.
    int temp = FlipCount / 2;

    NumCounts[9] = temp;
    NumCounts[6] = FlipCount - temp;

    int SetCount = 0;

    // 0부터 9를 순회하여 필요한 세트 수를 구한다.
    for (int i = 0; i < 10; ++i)
    {
        if (SetCount < NumCounts[i])
        {
            SetCount = NumCounts[i];
        }
    }

    std::cout << SetCount;

    return 0;
}

성능 요약

시간 복잡도는 $O(d)$입니다.

• 자릿수만큼 반복되는 반복문 $O(d)$
  • d는 자릿수만큼 반복되는 횟수를 의미합니다.
• 결과를 출력하는 반복문 $O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

메모리: 2020 KB

시간: 0 ms