백준 2668 숫자고르기

www.acmicpc.net/problem/2668

2668번: 숫자고르기

이 문제는 그래프 탐색, 깊이 우선 탐색 등으로 분류되어 있는데, 필자는 집합을 활용한 풀이를 생각했다.

 

첫 번째줄은 항상 1부터 N까지이고, 

두 번째 줄에는 랜덤으로 숫자가 배치된다. 

 

각 줄을 집합으로 묶어주고, 비교를 통해 같은지 판단하면 된다. 중요한 점은 항상 첫 번째 줄에는 모든 숫자가 등장하지만, 두 번째 줄에는 숫자들이 선택적으로 등장한다. 따라서 첫번째 줄을 순회하면서 두 번째 줄에 포함되는지 확인하고, 그렇지 않으면 제외하는 식으로 해결할 수 있다.

 

<주요 내용>

집합

 

<코드>

 

파이썬 버전

import sys
si = sys.stdin.readline


def main():
    cards = {}
    n = int(si())
    for i in range(1, n+1):
        cards[i] = int(si())
    top = set(cards.keys())
    bottom = set(cards.values())
    while top != bottom:
        cnt = 0
        for e in top:
            if e not in bottom:
                cnt += 1
                del cards[e]
        top = set(cards.keys())
        bottom = set(cards.values())
        n -= cnt

    print(n)
    top = list(top)
    top.sort()
    for e in top:
        print(e)
    return


if __name__ == '__main__':
    main()

 

C++ 버전

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
using namespace std;
const int sz=1e2+1;
int n,nmap[sz];
vector<int>v;
unordered_map<int,int>umap;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>nmap[i];
        v.push_back(i);
        if(umap.find(nmap[i])==umap.end()){
            umap[nmap[i]]=1;
        }else umap[nmap[i]]++;
    }
    auto it=v.begin();
    while(it!=v.end()){
        auto e=v[it-v.begin()];
        if(umap.find(e)==umap.end()){
            v.erase(it);
            umap[nmap[e]]--;
            if(!umap[nmap[e]])umap.erase(nmap[e]);
            it=v.begin();
        }else it++;
    }

    cout<<v.size()<<endl;
    sort(v.begin(),v.end());
    for(auto e:v)cout<<e<<endl;
    return 0;
}