[BOJ/C++] 13144 List of Unique Numbers : Two Pointer

문제

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

풀이

문제 보자마자 조합 문제인 줄 알고, 어떻게 풀이해야 하는지 감이 안왔었는데 중복이 없는 연속 수열을 찾는 투 포인터 문제였다.

• start 포인터와 end 포인터로 순회하면서 탐색

• 수열이 1 2 3 1 2인 경우, 각각 중복이 없는 구간은
  1 2 3 1 2
  1 2 3 1 2
  1 2 3 1 2
  1 2 3 1 2
  1 2 3 1 2

• 결과값에 각 경우에 end-start를 더한다.
  start=0, end=3인 경우,
  1 1 2 1 2 3 세 가지의 수열이 가능하기 때문
  🛑코드 로직을 보면 1 2 3 구간의 경우, end는 3까지 증가하고 break문으로 감

⚠️start가 0 1 2 순으로 증가하며 for문 돌 때, end가 기존 범위보다 작아지는 경우는 없으므로 end를 초기화하지는 않아도 됨

코드

#include <iostream>

using namespace std;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	int end = 0;
	long res = 0;

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

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

	cout << res;
}