[백준] 13701번 중복제거 (C++)

https://www.acmicpc.net/problem/13701

 

 

이 문제는 정수가 입력될때 이전에 나왔던 정수에 대해서 나왔는지 안나왔는지 판별하여 처음 나왔을 경우

정수를 출력 나오지 않은 경우 출력하지 않는 문제이다.

 

즉 입력된 순서를 유지하되 이전에 나왔던 정수에 대해선 제거해야한다.

 

이때 문제의 메모리 제한을 보면 8MB이다. 정수형 배열을 선언하여 500만개를 할당받을 경우

4byte * 500만이기 때문에 대략 20MB 정도 된다. 

 

이를 줄이기 위해 최대 공간복잡도 5MB인 bool 형 배열을 할당받아야 한다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int N;
vector<bool> v(1 << 25);

void input() {
    while(cin >> N) {
        if(!v[N]) {
            cout << N << ' ';
            v[N] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}

 

input함수를 살펴보자

void input() {
    while(cin >> N) {
        if(!v[N]) {
            cout << N << ' ';
            v[N] = true;
        }
    }
}

 

코드가 굉장히 짧은데 입력받은 수에 대해서 있는지 없는지만 확인하여

있는 경우 건너 뛰고 있지 않은 경우 입력 받은 수를 출력하고

방문체크를 한다.