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

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

13144번: List of Unique Numbers

 

문제 분석

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다.

이중 for문으로 문제를 풀고자 한다면, N이 최대 10만이기 때문에 O(N^2)이 소요되므로 시간 내에 해결할 수 없다.

 

투 포인터를 사용해 문제를 해결할 수 있다.

 

코드

#include <iostream>
#include <set>

using namespace std;

int n;
int arr[100000];
bool isContain[100001];
unsigned long long result;

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int start = 0;
    int end = 0;

    for (start = 0; start < n; start++) {
        while (end < n) {
            if (isContain[arr[end]]) {
                break;
            }
            isContain[arr[end]] = true;
            end++;
        }

        result += end - start;
        isContain[arr[start]] = false;
    }

    cout << result << "\n";
    return 0;
}

 

코드 설명

arr 배열에는 입력으로 받은 수열이 들어가고, isContain 배열은 수열을 순회하면서 해당 숫자가 투 포인터에 의한 탐색 구간에 포함되었는지를 체크하기 위한 용도로 사용된다.

 

초기 조건으로 start, end를 0으로 설정하고 시작한다. 우리는 이런 방법으로 검사할 것이다.

 

1. arr[end]가 현재 투 포인터를 통해 보고 있는 구간 안에 등장한 적이 없다면, end를 증가시킨다.

2. 만일 arr[end]가 현재 투 포인터를 통해 보고 있는 구간 안에 등장한다면, result에 end - start를 더한다. [start, end) 구간 안에서 만들 수 있는 수열의 개수가 end - start이기 때문이다.

3. result에 더해준 후, isContain[start]를 false로 해제한다.

 

이 과정을 start가 [0, n) 인 구간에 대해 반복해 수행하면 문제가 해결된다.

 

최근 취업준비를 하면서 자소서를 쓰느라 알고리즘을 안 풀었더니 또 머리가 잘 안 굴러간다. 비상 ... !