[백준] 1475번 방 번호

 

 

문제

소스코드

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
 
int main() {
    std::string N{};
    std::vector<char> vector;
    int minimumCount{ 0 };
 
    std::cin >> N;
    for (auto& word : N)
        vector.emplace_back(word);
 
    // 1 Set(0~9)
    bool setList[10]{ false };
 
    while (vector.size() != 0) {
 
        //One Cycle
        for (auto iter = vector.begin(); iter != vector.end();) {
            int number = *iter - '0';
 
            //6<--->9 예외처리
            if (number == 6 || number == 9) {
                if (!(setList[6] && setList[9])) {
                    if (setList[6] == false) {
                        setList[6] = true;
                    }
                    else {
                        setList[9] = true;
                    }
                    iter = vector.erase(iter);
                    continue;
                }
            }
 
            if (setList[number] == false) {
                setList[number] = true;
                iter = vector.erase(iter);
            }
            else {
                ++iter;
            }
        }
        ++minimumCount;
        memset(setList, false, sizeof(setList));
    }
    std::cout << minimumCount << "\n";
}

 

후기

이 문제를 해결하기 위한 키워드는  필요한 최솟값을 구하는 것이다.

 

0-9까지의 숫자가 나왔는지 판단할 수 있는 bool 형태의 setList를 만들어서 매 Cycle 마다 Vector에 요구하는 숫자가 있으면 Vector를 지우고 

SetList를 다시 초기화하여 Vector.size()가 0이 될 때까지 반복해서 풀었다.

 

이 방법은 Vector를 당기기도 하고 N^2의 시간 복잡도를 가지기 때문에 경우에 따라서는 시간 초과가 생길 수 있다.

 

여기서는 요구하는 숫자 단위와 제한 시간이 여유가 있어 통과하였고 만약 메모리와 시간이 제한적이라면

동적 프로그래밍, 비트 연산자를 사용하면 될 거 같다.

 

 

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/1475