[C++ 백준 풀이] 1436번 : 영화감독 숌 / 1966번 : 프린터 큐 / 2164번 : 카드2 (우선 순위 큐, priority queue)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1436번 : 영화감독 숌에 대한 풀이 코드와 해설을 다루고 있습니다.

문제들의 난이도는 Solved.ac 기준 Silver V ~ III 정도로 분포되어 있습니다.

 

 

1436번 : 영화감독 숌

 

문제 풀이에 정확히 필요한 부분만 편집했습니다.

문제를 요약하면 666이라는 숫자가 부분 수열로 나타나는 수들을 종말의 숫자라고 정의할 때, 입력받은 N에 대해 N번째 종말의 숫자를 출력하는 문제입니다.

수의 입력 범위가 N이 최대 10000이므로, 모든 숫자들에 대해 검증을 하는 브루트포스 알고리즘으로 풀어도 풀 수 있는 문제입니다.

 

 

↓ 코드 원문은 아래 접은 글에 있습니다.

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

int main() {
    int N, check, i = 100, cnt = 0;
    string str;
    cin >> N;
    while(cnt < N) {
        i++;
        str = to_string(i);
        check = 0;
        for(int j=0; j<str.length()-2; j++) {
            if(str[j] == '6' && str[j+1] == '6' && str[j+2] == '6') {
                check = 1;
                break;
            }
        }
        if(check) cnt++;
    }
    printf("%d", i);
}

 

cnt를 이용해 '종말의 숫자'가 지금까지 몇 개 카운트 되었는지를 계산합니다.

i는 가장 작은 세 자리수인 100부터 시작해서, 1씩 증가시켜 가면서 모든 i에 대해 종말의 숫자인지를 확인합니다.

확인 과정은, string 헤더 파일의 to_string 함수를 이용하여 정수를 문자열로 변환시킨 뒤, 모든 자릿수를 검사하여 6이 연속으로 3개 나왔는지를 통해 진행했습니다.

세 자리 연속으로 6이 나오면 check를 통해 cnt를 1 증가시켰습니다.

cnt가 N에 도달하면 break가 발생하고, i를 출력하게 됩니다.

 

 

채점을 수행해보면, 브루트포스 알고리즘으로 구현했음에도 60ms라는 넉넉한 시간에 풀이가 완료됨을 확인할 수 있습니다.

브루트포스 알고리즘으로 탐색을 수행할 때는 견적이 나올만한지 잘 판단하고 들어가는 것이 중요하다고 생각합니다.

 

 

1966번 : 프린터 큐

 

프린터 큐를 정의하고 이를 구현하여 각각의 테스트케이스에 대해 특정 문서가 몇 번째로 출력되는지를 구하는 문제입니다.

이를 계산하는 식을 만들기보다는 프린터 큐를 직접 구현해서 세보라는 문제입니다.

중요도에 따라 인쇄 여부가 결정되기 때문에, C++ queue 헤더파일에 포함되어있는 priority queue(우선순위 큐)를 이용하면 그렇지 않은 경우보다 훨씬 쉽게 해결이 가능합니다.

 

 

↓ 접은 글에 풀이 코드 원문이 있습니다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int T, N, M, val, temp_idx, temp_val, cnt;
    cin >> T;
    for(int i=0; i<T; i++) {
        cin >> N >> M;
        queue<pair<int, int>> doc;
        priority_queue<int> doc_priority;
        cnt = 0;
        for(int j=0; j<N; j++) {
            cin >> val;
            doc.push({j, val});
            doc_priority.push(val);
        }
        while(!doc.empty()) {
            temp_idx = doc.front().first;
            temp_val = doc.front().second;
            doc.pop();
            if(temp_val == doc_priority.top()) {
                doc_priority.pop();
                cnt++;
                if(temp_idx == M) break;
            }
            else doc.push({temp_idx, temp_val});
        }
        cout << cnt << "\n";
    }
}

 

우선 queue와 priority_queue 두 개를 모두 선언하고, 각각에 대해 입력값을 대입해줍니다.

queue에는 입력 순서와 중요도를 push 해주고, priority queue에는 중요도만 push 해줍니다.

그 다음 pair queue의 원소들을 하나씩 pop 해주면서 priority queue의 front에 있는, 그러니까 큐에 들어있는 원소들 중에 가장 가치가 높은 것인지를 확인합니다.

만약 맞다면 그대로 pop을 진행해주고, 아니라면 pop한 것을 다시 push 해주어야 합니다.

 

 

4ms만에 프로그램이 모든 테스트케이스를 통과한 것으로 보아 C++ 라이브러리로 구현된 priority_queue의 성능이 아주 좋은 것 같습니다.

 

 

2164번 : 카드2

 

이 문제는 큐를 직접 구현하라고 만들어준 문제인 것 같지만, 그래도 큐 라이브러리를 써서 풀어보겠습니다.

맨 위의 카드 하나는 버리고, 하나는 밑으로 다시 넣는 과정을 반복할 때 마지막으로 남는 카드를 구하는 문제입니다.

 

 

↓ 풀이 코드 텍스트 원문은 하단에 있습니다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int N, temp;
    cin >> N;
    queue<int> card;
    for(int i=1; i<=N; i++) card.push(i);
    while(1) {
        temp = card.front();
        card.pop();
        if(card.empty()) break;
        temp = card.front();
        card.pop();
        if(card.empty()) break;
        card.push(temp);
    }
    cout << temp;
}

 

풀이 코드는 위와 같고, queue를 선언하여 queue에 순서대로 push 해줍니다.

그 다음 pop 하기 전에 front의 카드를 temp에다가 저장하고 pop을 해야 empty가 떴을 때 마지막으로 버린 카드를 알 수 있습니다.

그 정도만 유의하면 나머지는 쉽게 구현이 가능합니다.

 

 

코드를 제출하여 채점해보면 4ms라는 짧은 시간에 채점이 완료된 것을 확인할 수 있습니다.