<백준 알고리즘>투포인터 (13144번)

투 포인터란?

말 그대로 무언가를 가리키는(point) 두가지인데 주로 연속된 데이터(ex.배열 ..)에서 사용되는 방식이다.

예를 들어 1 3 4 5 2라는 배열이 있고 start pointer = sp와 end pointer = ep있다고 한다.

이때 처음에 sp와 ep는 둘다 0번째를 가리키고 있다. 만약 구해야 하는 것이 배열에서 합이 7이되는 구간의 인덱스라면

ep를 하나씩 올려가며 sp = 0 ep = 2이 될 때 합이 7을 넘어가므로 sp를 한 칸 올려주면 sp = 1, ep = 2이 되고 이때 합이 7이므로 이 인덱스를 저장한다. 같은 방식으로 ep를 올리면 또 합이 7을 넘으므로 sp를 올리고 하다보면 sp = 3, ep = 4일 때 합이 7이 되어 이 인덱스를 저장한다.

이런 식으로 사용하는 것이 투포인터이다.

백준 13144번

접근 방법

1. 처음엔 입력을 받을 때 특정 값이 반복되며 그 값에 해당하는 인덱스를 각각 벡터에 저장해주어 나중에 범위를 구하면 된다고 생각하였다. 이 방법으로 구현하니까 포함이 되지 않는 경우가 존재하여 답이 안나왔다.(이렇게 푸는 방법이 있을 수도 있지만 나는 생각해내지 못했다.)

2. 그렇게 고민하다 투포인터를 이용하여 풀 수 있다는 것을 알 수 있었다. 전체 경우를 구한다음 중복되는 경우를 빼주는 방식으로 구하였다. 중복되는 경우를 찾기 위해서 투포인터를 이용한다.
   먼저 방문한 수에 대한 여부를 배열에 저장하고 이미 있는 수를 또 방문한다면 중복이니까 N - rightPointer를 해주었다.(현재 경우에 나올 수 있는 중복되는 경우의 수) 그 다음에 left pointer의 방문여부를 0으로 만들어 준다. 같은 방식으로 진행한 다음 전체 경우의 수 - 전체 중복 경우의 수를 해준다.

2-1. 1번 접근 방식과 다른 점은 배열의 처음부터 진행하며 빠지는 경우 없이 다 구할 수 있다는 점인 것 같다.

코드 구현할 때 변수의 자료형으로 long long을 써야한다. 경우의 수가 매우커지기 때문에..

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <deque>



using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0, 0, 1, -1 };

long long N;
int isVisited[100001] = { 0 };
int nums[100001] = { 0 };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	long long totalCnt = (N * (N + 1)) / 2;

	for (int i = 0; i < N; i++)
	{
		
		cin >> nums[i];
	
	}

	long long totalExept = 0;

	int lp = 0;
	int rp = 1;
	isVisited[nums[lp]] = 1;

	while (rp < N)
	{

		if (isVisited[nums[rp]] == 1)
		{
			isVisited[nums[lp]] = 0;
			totalExept += N - rp;
			lp++;
		}
		else
		{
			isVisited[nums[rp]] = 1;
			rp++;
		}
	}

	cout << totalCnt - totalExept;

	return 0;
}