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

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

• 정답에 대한 자료형에 대해 신경써야했다(십만단위 배열에 대한 연산이므로 당연)

1. 수열에서 연속한 1개 이상의 수 -> 투 포인터(정렬에 대한 언급이 없으므로 거의 확정)
2. 여러 번 등장하지 않는 경우 -> 투 포인터로 끝 자리를 방문했는지 여부를 확인(확정)

• for문으로 시작 지점을 매 번 갱신하고, en변수를 별도로 초기화되지 않도록 하여 배열의 길이를 즉시 파악할 수 있도록 함
• 이후 각 for문의 연산 끝에서 en - st를 통해 해당 시점에서 얻을 수 있는 수열의 수를 누적 가능

#include<iostream>
#include<cstring>
using namespace std;

int n;
int a[100001];
bool vis[100001]{ 0 };

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

void solution() {
	input();
	int en = 0;
    long long answer = 0;
	for (int st = 0; st < n; ++st) {
		while (en < n) {
			if (vis[a[en]]) break;
			vis[a[en++]] = 1;
		}
		answer += en - st;
		vis[a[st]] = 0;
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}