문제

문제 링크

해설

• 수열의 길이가 최대 10만이므로, (O(N²)이 소요되기 때문에) bruteforce하게 문제를 풀면 안 된다는 것을 알 수 있습니다.
• 우선 연속해서 더할 구간의 시작점(left)과 끝점(right) 이라는 아이디어는 분명히 좋은 아이디어니까, 이 투포인터를 어떻게 하면 라인스위핑 알고리즘으로 더욱 빠르게 최적해를 구할 수 있을지 아이디어를 생각해봅시다.
• 수열의 왼쪽부터 차례대로 연속해서 수를 뽑다가, 이미 등장한 수를 뽑았을 경우에는 어떻게 해야 할까요?
  • {1, 2, 3}까지 뽑았을 때는 1, 2, 3, {1, 2}, {2, 3}, {1, 2, 3}으로 7가지 경우의 수를 얻을 수 있습니다. 즉, 등차수열의 합의 개수와 같습니다.
  • {1, 2, 3, 1}로 이미 등장한 수를 뽑았을 경우에는, 범위의 시작점인 left를 한 칸 오른쪽으로 당겨줍니다.
    • 즉, 맨 왼쪽의 1을 버리겠다는 뜻입니다.
    • 동시에, 맨 왼쪽의 1을 포함할 때 만들 수 있던 연속합의 경우의 수는 정답에 더해줍니다.
    • 뭐가 있죠? 1, {1, 2}, {1, 2, 3} 3개가 있겠네요.
    • 즉, right - left개 경우의 수가 생깁니다.
• 위와 같은 일련의 과정을 거치다보면, 결국에는 아무런 수도 겹치지 않는 구간 [left, right] 을 얻을 수 있습니다.
• 이 구간은 앞서 말했듯 등차수열의 합 개수만큼의 경우의 수가 나옵니다.
• 따라서 (right - left) * (right - left + 1) / 2를 합산합니다.
• 이렇게 O(N)에 문제를 풀 수 있는데, 이 과정에서 정답이 int 범위를 넘을 수도 있습니다. (일례로 10만개의 수가 모두 다르면, int 범위를 넘게 됩니다.)
• 그러므로, 정답을 저장하는 변수는 unsigned long long으로 선언합니다.

코드

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	
	size_t N;
	cin >> N;
	
	vector<int> arr(N);
	for (size_t i = 0; i < N; ++i) cin >> arr[i];
	
	unsigned long long answer = 0;    // int 범위를 넘을 수 있다.
	size_t left = 0, right = 0;		  
    
    vector<bool> check(N, false);    // 중복된 숫자 발견하기 위한 용도
    
	while (right < N) {
		if (!check[arr[right]]) check[arr[right++]] = true;
		else answer += (right - left), check[arr[left++]] = false;
	}
	answer += (right - left) * (right - left + 1) / 2;
	cout << answer << '\n';
}

소스코드 링크

• 코드에서 주의할 점이 있는데, 코드 마지막에 변수 answer에 등차수열의 합 공식 결과물을 합산하는 부분이 있습니다.
• 이 과정에서 2를 나눌 때 left, right 변수가 int 였다면, 암묵적 캐스팅이 발생할 수 있습니다. 따라서 (unsinged long long) 또는 static_cast<unsigned long long>() 또는 size_t 자료형을 사용해서 암묵적 캐스팅이 발생하지 않도록 막아주셔야 정답처리가 되실 겁니다.

결과