[백준] 13144번: List of Unique Numbers C++ 풀이

문제

문제 분류

투 포인터

📌 풀이 방법

먼저, 예제 2번을 보면 5개의 숫자가 1, 2, 3, 1, 2 로 배열을 이루고 있습니다.
이 경우에서 연속한 배열을 뽑았을 때 중복이 없는 경우는 아래와 같습니다.

1, 12, 123
2, 23, 231
3, 31, 312
1, 12
2

 

위와 같은 구성으로 이루어지며 이 경우를 보면 시작하는 수(start)로 부터 중복되는 수(end)가 등장하는 순간까지의 경우를 모두 더하면 됩니다.
즉, 각 start마다 end - start 만큼의 경우가 존재한다는 의미입니다.
그러니 우리는 start 인덱스를 0부터 N-1까지 진행하면서 중복되는 수가 있는지 확인하면 됩니다.

1. 0부터 N-1 인덱스를 순차적 탐색한다.
2. 각 인덱스를 탐색하는 중간에 중복되는 수를 확인한다.
3. 중복되는 수가 없다면 end를 1씩 증가시킨다.
4. 중복되는 수가 있다면 end - start 만큼 더한다.

정답 코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N;
    cin >> N;

    vector<int> arr(N);
    vector<bool> visited(N, false);
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    if (N == 1)
    {
        cout << 1;;
        return 0;
    }

    int end = 0;
    long result = 0;

    for (int start = 0; start < N; ++start)
    {
        while (end < N)
        {
            if (visited[arr[end]])
            {
                break;
            }
            visited[arr[end]] = true;
            ++end;
        }
        result += end - start;

        visited[arr[start]] = false;
    }

    cout << result;
}

참고 사이트

https://velog.io/@sammool/BOJ-C-13144-List-Of-Unique-Numbers