[G4] 백준 13144번 List of Unique Numbers C++ 투 포인터

리뷰

 

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

 

투 포인터로 포인터를 옮겨가며 방문처리를 하고 두 포인터 위치의 차이를 더해주는 문제

최악의 케이스의 경우 int의 범위를 넘어가므로 long long타입으로 ans를 지정해 주어야 한다.

 

 

전역 변수

• n : 수열의 길이를 저장할 변수
• nodes : 수열 정보를 저장할 변수
• v : 각 수를 방문처리할 변수, 최대 10만이 들어오므로 그거보다 크게 세팅해 준다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 수를 nodes배열에 입력받아 준다.
2. 두 포인터 l, r을 0으로 초기화 해주고, 정답 변수 ans를 0으로 초기화 해준다.
3. r이 n범위 내에 있을때 동안 반복문을 실행해 준다.
4. 만약 현재 r포인터가 있는 수가 방문하지 않았다면 ans에 r - l + 1을 더해주고, 방문처리 후 r을 다음위치로 이동한다.
5. 만약 방문한 수라면 방문이 해제될때까지 l을 증가시키며 옮기면서 방문을 해제해준다.
6. 탐색을 마친 후 ans에 저장되어있는 값을 출력해 준다.

 

참고 사항

ans는 long long타입이어야 한다.

 

 

정답 코드

#include<iostream>
using namespace std;

int n;
int nodes[100000];
int v[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> nodes[i];
	int l = 0, r = 0;

	long long ans = 0;
	while (r < n) {
		if (!v[nodes[r]]) {
			ans += r - l + 1;
			v[nodes[r++]]++;
		}
		else {
			while (v[nodes[r]]) v[nodes[l++]]--;
		}
	}
	cout << ans;
}