백준 16466번 콘서트

문제 링크입니다: https://www.acmicpc.net/problem/16466

우선순위 큐를 이용해서 간단히 풀 수 있는 문제라고 생각했지만 생각보다 함정이 많았던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 티켓팅 번호가 중복될 경우가 있으므로 map을 이용하여 중복해서 우선순위 큐에 넣어지지 않도록 합니다.

2. 티켓 번호는 1부터 시작하므로 우선순위 큐의 root를 idx와 비교하고 idx와 root가 다를 경우 idx가 답이므로 출력하고 프로그램을 끝냅니다.

3. 1~N까지 다 티켓팅이 완료되었을 경우 2번에서 값이 출력되지 않습니다. 따라서 2번에서 끝나지 않을 경우를 대비해 while문 밖에서 idx를 출력하는 문장을 추가해줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <functional>

#include <map>

using namespace std;

 

map<unsigned int, int> visited;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        priority_queue<unsigned int, vector<unsigned int>, greater<unsigned int>> pq;

        for (int i = 0; i < N; i++)

        {

                 unsigned int num;

                 cin >> num;

 

                 //중복된 숫자를 넣지 않는다

                 if (!visited.count(num))

                 {

                         visited[num] = 100;

                         pq.push(num);

                 }

        }

 

        unsigned int idx = 1;

        while (!pq.empty())

        {

                 unsigned int cur = pq.top();

                 pq.pop();

                 if (cur != idx)

                 {

                         cout << idx << "\n";

                         return 0;

                 }

                 idx++;

        }

        //idx와 cur이 전부 다 같았을 경우

        cout << idx << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~