알고리즘(내방식)
- 숫자를 왼쪽에서 오른쪽으로 살펴가면서, 그 수가 나온 인덱스를 기록(saveIdx)한다.
- i를 기록할때 이미 기록된 인덱스가 있을 경우, 그 인덱스부터 이전에 체크가 안된 인덱스들은 i 까지만 연속해서 숫자를 뽑을 수 있다. 따라서 이에 해당하는 경우의 수를 정답에 추가시켜준다.
알고리즘(투포인터)
내가 한 방식에서 관점만 바꾸면 투포인터 방법이 된다.
왼쪽에서 오른쪽으로 end를 하나씩 늘려가며 숫자를 살펴가면서, 현재 수를 체크한다.
- 만약 i에서의 숫자가 이미 체크 되었을 경우, start 에서부터 그 체크된 숫자(c)까지는 end 이전까지만 연속해서 숫자를 뽑을 수 있다.
- 따라서 start를 c까지 늘려가며 경우의 수를 추가하고, check를 풀어가면 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
int n, nums[100010], saveIdx[100010];
long long ans;
bool check[100010];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> nums[i];
for (int i = 1; i <= n; i++) {
if (saveIdx[nums[i]] != 0) {
for (int j = saveIdx[nums[i]]; j >= 1; j--) {
if (!check[j]) {
ans += (i - j);
check[j] = true;
saveIdx[nums[j]] = 0;
}
else
break;
}
}
saveIdx[nums[i]] = i;
}
for (int i = n; i >= 1; i--) {
if (!check[i]) {
ans += (n + 1 - i);
check[i] = true;
}
else
break;
}
cout << ans;
}