Bin_S+StudyRoom

• 문제

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

• 입력

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

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

• 출력

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

• 예제 입력

5
1 2 3 4 5

5
1 2 3 1 2

5
1 1 1 1 1

• 예제 출력

15

12

5

• 접근방식

중복되는 수를 체크하는 배열이 필요할 것으로 보이고 시작지점 startNumebr부터 시작해서 중복되는 수가 나오면 endNumber로 저장해두고 startNumber를 증가시키면서 경우의 수를 구하는 것으로 접근했다.
등차 수열의 합의 공식을 사용해서 n(n+1)/2를 더하면 된다.

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

long long n, startNumber, endNumber, check[100004], a[100004], result;

int main()
{
    cin >> n;

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

    while (endNumber < n)
    {
        if (!check[a[endNumber]])
        {
            check[a[endNumber]]++;
            endNumber++;
        }
        else
        {
            result += (endNumber - startNumber);
            check[a[startNumber]]--;
            startNumber++;
        }
    }
    
    result += (long long)(endNumber - startNumber) * (endNumber - startNumber + 1) / 2;
    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/13144