[C++] BOJ(백준) 13144 List of Unique Numbers

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

13144번: List of Unique Numbers

 

투 포인터 문제다.

중복이 없는 수열의 시작과 끝 + 1을 투 포인터로 찾으려고 했다.

1 2 3 4 1 2 의 경우 start = 0, end = 4까지 연산을 거치고

이 때 1 / 1, 2 / 1, 2, 3 / 1, 2, 3, 4의 4가지 수열이 나온다.

2, 3 / 2, 3, 4 / 3, 4 등도 존재하지만 중복 계산을 방지하기 위해 start의 값을 포함하는 수열만을 계산했다.

 

방법은 금방 찾아냈는데 코드를 구현하는 방법이 잘 떠오르지 않아 오래걸렸다.

 

#include <iostream>
using namespace std;

int n, s, e;
long long res;
int arr[100000];
bool visit[100001];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	
	for (s; s < n; s++) {
		while (e < n) {
			if (visit[arr[e]]) break;
			visit[arr[e++]] = true;
		}
		res += (e - s);
		visit[arr[s]] = false;
	}
	cout << res;
}

투 포인터는 기본적으로 while을 사용했는데 for를 사용하는게 더 편할 수도 있다는 걸 깨달았다.