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

문제

13144번: List of Unique Numbers

풀이

두 포인터 문제이다.

 

• 두 포인터를 이용하여 start를 포함하며 반복되는 수가 없는 수열의 경우의 수를 계산하는 방식으로 해결한다.
• start부터 중복되는 수가 없을 때까지 end를 늘린다. 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다.
• start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start개이다. 이 개수를 answer에 추가한다. 
• 그 다음, start를 앞으로 늘려서 1번부터 반복한다. 

코드

#include <iostream>

using namespace std;

int nums[100000];
bool num_count[100001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

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

    long long answer = 0;
    int start = 0;
    int end = 0;
    while (true)
    {
        // start를 더 이상 늘릴 수 없을 때까지 반복한다.
        if (start >= N)
        {
            break;
        }

        // start부터 중복되는 값이 없을 때까지 수열을 늘린다.
        // 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다.
        while (end < N && num_count[nums[end]] == false)
        {
            num_count[nums[end]] = true;
            end++;
        }

        // start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start이다.
        answer += (end - start);

        // start를 앞으로 늘린다.
        num_count[nums[start]] = false;
        start++;
    }

    cout << answer;

    return 0;
}