[백준/BOJ] 백준 13144번 : List of Unique Numbers

www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

투 포인터를 이용하여 문제를 해결했는데, set<int> check에 투 포인터 구간의 값을 저장하여 구간에 수가 겹칠 때를 찾았다. 체크하는 right가 구간에 겹치지 않는 수라면, right의 수를 check에 넣고, right를 증가시키고, 체크하는 right가 구간에 겹치는 수 라면, 지금 left가 가장 왼쪽에 무조건 포함된 연속한 경우의 구를 더한다((right - 1) - left + 1) 그리고 left를 오른쪽으로 한칸 옮긴다. 그렇게 right의 위치가 n이 된다면 투 포인터의 이동은 끝나고, 투 포인터의 이동이 끝났을 때 상황의 left와 right를 고려해서 그때의 경우의 수도 넣어야 되는데, 그때 구간의 길이가 2 이상인 경우, 해당 수를 각각 하나 고르는 경우와 구간중 2개의 수를 골라서 구간을 만드는 경우를 고려해야 되고, 구간의 길이가 1 이하인 경우, 해당 수를 각각 하나 고르는 경우를 고려한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n;
vector<int> input_data;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		input_data.push_back(input);
	}

	set<int> check;
	set<int>::iterator it;

	int left = 0;
	int right = 0;
	long long result = 0;
	while (1)
	{
		//체크하는 구간에 겹치지 않는 수 일때
		if (check.count(input_data[right]) == 0)
		{
			check.insert(input_data[right]);

			right++;
		}

		//체크하는 구간에 겹치는 수 일때
		else
		{
			//지금 left가 가장 왼쪽에 무조건 포함된 연속한 경우의 구를 더한다
			result += (long long)((right - 1) - left + 1);

			//left를 오른쪽으로 한칸 옮긴다
			it = check.find(input_data[left]);
			check.erase(it);
			left++;
		}

		if (right == n)
			break;
	}

	//현재 구간의 길이가 2 이상인 경우, 해당 수를 각각 하나 고르는 경우와
	//구간중 2개의 수를 골라서 구간을 만드는 경우를 고려한다
	if (((right - 1) - left + 1) >= 2)
	{
		//해당 수를 각각 하나 고르는 경우
		result += (long long)((right - 1) - left + 1);

		//구간중 2개의 수를 골라서 구간을 만드는 경우
		result += (long long)(((long long)((right - 1) - left + 1) * (long long)(((right - 1) - left))) / 2);
	}

	else
	{
		//해당 수를 각각 하나 고르는 경우
		result += (long long)((right - 1) - left + 1);
	}

	cout << result;

	return 0;
}