백준 13144 List of Unique Numbers 풀이 (C++)

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

32 MB

11798

4279

3077

34.461%

문제

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

입력

첫 번째 줄에는 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

출력

조건을 만족하는 경우의 수를 출력한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

long long N, iResult = 0;
long long llCount[100'001];
long long llNum[100'001];


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> llNum[i];

    long long temp1= 0, temp2 = 0;
    while (temp1 < N)
    {
        if (!llCount[llNum[temp1]])
        {
            ++llCount[llNum[temp1]];
            ++temp1;
        }
        else
        {
            iResult += (temp1 - temp2);
            --llCount[llNum[temp2]];
            ++temp2;
        }
    }
    iResult += (long long)(temp1 - temp2) * (temp1 - temp2 + 1) / 2;
    cout << iResult;

    return 0;
}

 

수열의 합 공식과 그리디를 이용하여 풀이