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

 해당 문제는 투포인터 문제의 간단한 응용버전이다. 처음에는 투포인터로 안풀어도 될 거 같아서 그냥 구현해서 풀었지만 당연히 시간초과가 나왔었다. 생각보다 반복문 돌려야하는 게 많았다... 

 아래 코드는 시간초과나온 틀린 코드다. (그냥 set 에 원소들을 넣어주고 사이즈가 내가 원했던 사이즈가 맞으면 정답 ans 카운트를 하나 증가시키는 식으로 구현)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
int arr[100005];
set<int> s;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int ans = 0;

    for (int gap = 2; gap <= N; gap++) {
        for (int i = 0; i + gap <= N; i++) {    // 시작점 반복.
            for (int j = i; j < i + gap; j++) {    //gap번 반복
                s.insert(arr[j]);
            }
            if (s.size() == gap) ans++;
            s.clear();
        }
    }

    cout << ans + N;
}

 생각해보면, 내가 짠 틀린코드의 시간복잡도는 O(N^3)이다. O(N^2)으로 할 수 있을 것 같았는데, 아이디어가 떠오르지도 않았고 틀린 길을 걸어가고 있다는 것 같아서 그냥 탈출했다.

 

 그래서 투포인터 방식을 생각했다. 변수 st, en 들을 0으로 초기화해두고, 중복되는 숫자가 없을 때까지 en을 증가시키면서 방문했다는 표시를 남기면서 수열 개수를 찾아내는 방식으로 구현했다. 

• 만약 en이 N-1까지 도달했다면 해당 st 인덱스에서 N-1까지는 중복 숫자가 없다는 의미가 된다.

 그리고 en 변수를 증가시키다가 N - 1(최대 인덱스)에 도달하거나 이미 방문한 숫자라면 en을 증가시키는 반복문을 탈출한 뒤, 정답 변수인 ans에 en - st 를 더해줬다. (아래 코드 참고)

 이렇게 투포인터로 작성하게 되면, O(N^2)의 시간복잡도로 구현할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
int arr[100005];
bool vis[100005];   // 숫자 방문여부 따지는 변수

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int en = 0;
    ll ans = 0;
    for (int st = 0; st < N; st++) {
        while (en < N) {
            if (vis[arr[en]]) break;
            vis[arr[en]] = 1;
            en++;
        }
        vis[arr[st]] = 0;
        ans += en - st;
    }
    cout << ans;
}