[C++] 백준(BOJ) - 13144 : List of Unique Numbers

17 Mar 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 13144 : List of Unique Numbers(링크)

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

입력

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

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

출력

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

알고리즘

1. 투포인터 알고리즘
2. 구현 - 등차수열의 합
3. 경우의 수

풀이

1. 중복된 배열을 셀 수 있는 cnt 배열 필요
2. 중복되지 않는 수까지의 부분집합의 수 = 등차수열의 합 $(n*(n+1))/2$

코드

// BOJ-13144 : List of Unique Numbers 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, s, e, cnt[100004], a[100004];
ll res;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	while (e < n)
	{
		if (!cnt[a[e]])
		{
			cnt[a[e]]++;
			e++;
		}
		else
		{
			res += (e - s);
			cnt[a[s]]--;
			s++;
		}
	}
	res += (ll)(e - s) * (e - s + 1)/ 2;
	cout << res << '\n';
	
	return 0;
}

평가

• 중복된 수를 체크하기 위한 카운팅 배열
• 등차수열의 합
• 경우의 수 문제의 경우 long long 자료형을 박고 시작하는 것도 팁