[알고리즘] C++ 백준 13144 List of Unique Numbers

백준 13144

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

13144번: List of Unique Numbers

풀이 전 나의 생각

길이가 N인 수열이 주어질 때, 1개 이상의 연속된 수를 뽑았을 때 

같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다.

 

조건

- (1 ≤ N ≤ 100,000)

- 수열에 나타나는 수는 모두 1 이상 100,000 이하

 

과정

수열 N이 10만의 범위로 주어지기 때문에 단순히 2중 for문을 이용한 풀이를 진행한다면

10만 * 10만의 계산 횟수로 시간 제한을 맞추지 못할 것이다. 

따라서 투 포인터를 사용한 풀이를 진행해야 한다.

 

수열의 수는 10만 이하기 때문에 int 형 배열로 설정하고 수열의 경우의 수를

누적해서 더해주는 공간은 10만 * (10만. 9만9999...) 으로 int 형의 범위를 넘기 때문에

long 데이터 타입으로 설정해준다.

 

 

1. 탐색할 수열의 시작 포인터를 설정해준다. 

for (int st = 0; st < N; st++)
	{
		...

 

2. 설정된 시작 포인터를 기준으로 중복된 값이 나올 때 까지 끝 포인터를 증가시켜 준다.

while (end < N)
{
	if (visited[arr[end]]) break;

	visited[arr[end++]] = true;
}

예를 들어 (1, 2, 3, 3, 4)의 수열이 있다고 가정하면

(1, 2, 3, 3) 일 때 3, 3이 중복되기 때문에 끝 포인터가 마지막 3의 위치인 3까지 증가한다.

 

 

3. 끝 포인터의 증가가 끝났다면 최종적으로 결과값을 더해준다.

res += end - st;
visited[arr[st]] = false;

2번의 풀이를 이어서 설명하자면

(1, 2, 3, 3)에서 중복된 수로 인하여 while문을 벗어났기 때문에 결과값을 더해준다.

end - st가 결과값이 되는 이유는 연속된 수가 중복되지 않을 때 까지 탐색하며 구한

(1), (1, 2), (1, 2, 3) 총 3개의 경우의 수가 end(3) - st(0) = 3이기 때문이다.

 

이러한 과정을 끝까지 진행한다면 문제에서 구하고자 하는

중복되지 않는 연속된 수를 얻을 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int arr[100001];
bool visited[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N;
	int end = 0;
	long res = 0;
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	for (int st = 0; st < N; st++)
	{
		while (end < N)
		{
			if (visited[arr[end]]) break;

			visited[arr[end++]] = true;
		}

		res += end - st;
		visited[arr[st]] = false;
	}

	cout << res;
}