[C++] List of Unique Numbers

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

13144번: List of Unique Numbers

 

풀이

 

유의한 점

1. 문제 및 투포인터 이해 확실히 하기

예제 1과 같이 1 2 3 4 5가 입력 되었을 때, 같은 수가 여러 번 등장하지 않는 경우의 수는 다음과 같음.

[ [1], [1 2], [1 2 3], [1 2 3 4], [1 2 3 4 5], [2], [2 3], [2 3 4], [2 3 4 5], [3], [3 4], [3 4 5], [4], [4 5], [5] ] 

 

예제2와 같이 1 2 3 1 2가 입력 되었을 때는 아래와 같음. 

[ [1], [1 2], [1 2 3], [2], [2 3], [2 3 1], [3], [3 1], [3 1 2], [1], [1 2], [2] ] 

 

찾아보니 전형적인 투 포인터 문제라고 한다.

같은 수가 나오지 않을 때 까지 R(right) 포인터를 오른쪽으로 이동 시키고, 같은 수가 존재하면 L(left)포인터를 오른쪽으로 이동시킨다. 또 같은 수가 여러 번 나오는지 확인하는 것은 배열(num_arr2)을 이용해서 확인하도록 하였다. L포인터를 오른쪽으로 이동시킬 때는 num_arr2[num_arr[L포인터]]값을 초기화 시켜야 하는 것을 유의했다.

 

2. long long 형 사용

  - 입력으로 받은 N개의 정수는 모두 1 이상 100,000 이하이고, N은 1 ≤ N ≤ 100,000이기 때문에 sum으로 들어올 수 있는 최대 값은 100,000 * 100,000이다. 따라서 long long int형을 사용하였다.

#include <iostream>
using namespace std;

int num_arr[100001];
int num_arr2[100001];
int N, sum;

void input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> num_arr[i];
	}
}

void solution()
{
	int R = 0;
	long long int sum = 0; // max가 100000인 수가 100000개 있을 수 있으므로 long long 사용 필요
	for (int L = 0; L < N; L++)
	{
		while (R < N)
		{
			if (num_arr2[num_arr[R]] == 1)
				break;
			num_arr2[num_arr[R]] = 1;
			R++;
		}
		sum += R - L;
		num_arr2[num_arr[L]] = 0;
	}
	cout << sum;
}

int main(void)
{
	input(); 
	solution();
}

---

처음 생각했던 알고리즘 및 문제점

try1

  - timeout이 발생하였음.

  - for문을 2번 돌아서 O(n^2)의 시간 복잡도가 소요된다.

  - N <= 100000이고 시간제한은 1초이다. 이중 for문을 돌면 약 10억번이 계산되고, 약 1억번 도는 데 1초가 걸린다고 한다.. 즉 1000초 걸려서 timeout이라고 한다.

//try 1 : time out
void solution()
{
	int R;
	bool flag = false;

	for (int L = 0; L < N; L++)
	{
		sum += 1; // only 1 component in current array
		R = L + 1;
		while (R < N)
		{
			flag = false;
			for (int i = L; i < R; i++)
			{
				if (num_arr[i] == num_arr[R])
				{ 
					flag = true;
					break;
				}
			}
			if (flag == true)
				break;
			else
			{
				sum++;
				R++;
			}
				
		}
		//cout <<"L : "<<L<<" sum : "<< sum<<"\n";
	}
	cout << sum;
}

---

try2

  - 1 2 2 3 과 같이 제일 처음 숫자가 아니라 중간에 같은 숫자가 있는 경우를 탐지하지 못함.
    -> 가지고 있는 수를 저장하는 배열을 필요로 함. 

// try 2 : 틀렸습니다.
void solution()
{
	int L = 0;
	int R = L + 1;
	int sum = 0;
	while (L < N)
	{
		if (num_arr[R] == num_arr[L] || R >= N)
		{
			sum += R - L;
			L++;
			if (R != N)
				R++;
			cout << "L : " << L << " sum : " << sum << "\n";
		}
		else
			R++;
	}
	cout << sum;
}

 

 

참고링크

https://lemonlemon.tistory.com/54

Big O notation 과 시간 제한 (보통 1초 제한이라고 하면 어느정도?)