문제 설명
길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.
https://www.acmicpc.net/problem/13144
제한 사항
풀이
문제를 요약하면, N개의 수가 주어지면 연속한 수를 고를 때 유일한 수만 포함되도록 고르는 경우의 수를 구해야 한다.
해당 문제는 투포인터를 이용하면 간단하게 해결할 수 있다.
시작점을 정하고 오른쪽으로 진행하면서 같은 수가 나오기 전까지 끝점을 옮긴다.
만약, 같은 수가 나온다면 (끝점 - 시작점) 개만큼의 경우의 수를 추가할 수 있다.
이후, 시작점을 오른쪽으로 한 칸 이동시킨다.
그리고 위 과정을 계속 반복한다.
끝점은 계속 유지하기 때문에 시작점을 바꿔도 다시 순회하는 일을 줄일 수 있다.
핵심은 중복을 체크하는 일이다.
자료구조를 통해 포함된 수를 세는 것도 방법이긴 하지만 시간이 오래 걸린다.
따라서, 문제에서 주어진 수의 범위(100,000)만큼의 vector를 통해 중복 체크를 할 수 있다.
한 가지 주의할 점은 정답의 범위가 크기 때문에 int가 아니라 long long으로 선언해야 한다.
전체 코드
#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>
using namespace std;
int N;
vector<int> nums;
vector<bool> visited(100'000 + 1);
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
nums.resize(N);
for (int i = 0; i < N; i++)
{
cin >> nums[i];
}
long long ans = 0;
int start = 0, end = 0;
for (; start < N; start++)
{
while (end < N)
{
if (visited[nums[end]]) break;
visited[nums[end]] = 1;
end++;
}
ans += (end - start);
visited[nums[start]] = 0;
}
cout << ans;
return 0;
}