[BaekJoon 13144] List of Unique Numbers

안녕하세요. 오늘은 백준 13144 List of Unique Numbers라는 문제를 풀어보도록 하겠습니다.

 

해당 문제는 아래의 링크에서 확인하실 수 있습니다.

https://www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

 

문제를 살펴보면,

 

어떠한 수열이 주어지고, 해당 수열에서 같은 숫자가 없는 수열의 개수를 출력하는 문제입니다.

 

우선 이중 포문으로 구현을 하게 되면 O(N^2)의 시간 복잡도를 갖게 됩니다.

N <= 100000이고 시간제한은 1초입니다. 당연히 N^2의 알고리즘은 사용하시면 안 됩니다.

 

실제로 O(N)이나 O(NlogN)의 알고리즘 중에 위 문제와 같이 부분 수열의 개수를 묻는 문제를 보시게 되면 쉽게 투 포인터를 떠올리실 수 있습니다.

 

투 포인터 알고리즘을 혹시 모르신다면 아래의 링크에 제가 정리해놓은 글이 있습니다. 참고하시기 바랍니다.

https://chanho0912.tistory.com/29?category=871243

[C++/Algorithm] 투 포인터, 구간 합 이해하기

 

알고리즘은 다음과 같습니다.

 

• start = 0, end = 0으로 초기화합니다.
• start를 n까지 for문 순회합니다.
• start값부터 시작하여 처음 같은 숫자가 나올 때까지 end를 증가시킵니다.
• end가 더 이상 진전할 수 없다면, end - start를 결괏값에 더해줍니다.
• * 만약에 1, 2, 3, 4, 5라는 수열이라면, start가 0일 때 end는 5까지 진행됩니다. 
• * 따라서 1, 12, 123, 1234, 12345의 5개의 수열이 생성될 수 있기 때문에 end - start를 더해줍니다.
• 현재 start값에 대한 모든 판단이 끝났다면, start값에 대한 방문처리를 해제해줍니다.
• 다음 start값에 대해 3~5 반복

 

<소스 코드>

#include<bits/stdc++.h>
using namespace std; 
int n;
unsigned long long res;
bool vis[100000+1];
int main(){
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++) cin >> v[i];
	
	int start=0, end=0;
	for(int start = 0; start < n; start++) {
		while(end < n) {
			if(vis[v[end]]) break;
			vis[v[end]]=1;
			end++; 
		}
		res+=(end-start);
		vis[v[start]]=0;
	}
	cout << res << endl;
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.