[C++][백준 13144] List of Unique Numbers

[문제]

13144번: List of Unique Numbers (acmicpc.net)

13144번: List of Unique Numbers

---

[문제 풀이]

우선 문제를 풀기 전에 문제 조건을 보면 주의해야 할 요소들이 보인다. 메모리 제한이 고작 32MB에다가 수열의 한계가 100,000이다.

즉, 평범한 방식으로는 시간 초과가 날테니 어떻게  풀어야 할지 고민해보자.

 

고민을 하다가 두 포인터 알고리즘을 이용하기로 하였다.

두 포인터 알고리즘을 사용해서 새로운 값이 이미 기존에 있는 값이라면 앞에서부터 시작대로 줄여나가기로 하였다.

그런데 안에 해당 내용이 있는지는 어떻게 찾을 수 있을까?

단순히 벡터에 넣는다면 find로 찾을시 최악으로 따지면 O(n) 이 걸리고 이진탐색을 사용하자니 매 순간 sort를 해주어야 한다.

그러니 처음부터 이진트리를 활용하기로 하였다.

 

map은 C++에 있는 rb트리 구조의 이진트리로 삽입을 할때에도 찾을 때에도 binary 구조이므로 시간 초과가 걸릴 문제에서 굉장히 용이하게 사용이 가능한 자료구조 형태이다.

그러니 map과 두 포인터 알고리즘을 결합해서 사용하기로 하였다.

 

* 주의사항 : 해당 문제에서 수열의 최대치는 100,000이고 숫자의 최대치도 100,000이다. 즉 100,000 * 100,000 을 하면 100억으로 int의 범위를 벗어난다. 정답을 int가 아닌 다른 자료형을 주자.

---

[코드]

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> sequence(n,0);
    for(int i = 0;i<n;i++){
        cin >> sequence[i];
    }

    //두 포인터 알고리즘을 이용
    int start = 0;
    int end = 1;
    map<int, bool> bomb; // 메모리 제한과 시간을 보니 이진트리를 써야할 것 같애서 rb트리 구조인 map 사용
    bomb[sequence[start]] = true; // 우선  제일 처음 값 입력
    long long answer = 1; // answer는 1개가 넣어졌으니 1로 시작. 또한, 범위가 int를 넘어설 수 있기에 long long으로 지정.

    while(start<end && sequence.size() > end){ //start가 end와 동등해 지기 전이면서 동시에 end가 벡터의 마지막 위치에 닿기 전까지 돌리기.
        if(bomb[sequence[end]] == true){ //만일 bomb에 이미 들어가 있다면
            bomb.erase(sequence[start]);
            start++; //start를 1 진격
        }
        if(bomb[sequence[end]] == false && sequence.size() > end){ //만일 end가 아직 안 들어가있고 동시에 size보다 end값이 작다면
            bomb[sequence[end]] = true; //bomb에 벡터의 end 위치 입력.
            answer += bomb.size(); //answer는 bomb 사이즈 만큼 더해주자.
            end++; // end를 1 진격
        }
    }

    cout<<answer<<endl;

    return 0;
}

도중에 bomb 사이즈를 줄여주는 부분을 bomb.erase가 아닌 bomb[sequence[start]] = false로 뒀다가 틀렸습니다 연타를 맞았다.

언제나 코드를 짤 때 주의하도록 하자.