[백준] 13144번 : List of Unique Numbers

문제

 

 

접근 방식

분명 이전 투포인터 문제들과 비슷한 문제라 쉽게 풀 수 있을거라 생각했는데

반환값의 범위를 잘못 생각해서 맞왜틀을 시전하느라 시간을 날려먹었다.

 

수열이 수의 범위가 1 ~ 100,000까지인 10만개의 수들로 이루어져 있어서

결과가 인트형으로 될줄 알았는데 혹시 싶어 long으로 바꿔보니 맞았다...

(왜 10만 * 10만을 10억으로 생각하고 있었지...새벽이라 정신줄을 놓고 했나보다)

{1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1}

 

위와 같은 수열이 주어졌을 때 중복되지 않는 수로만 이루어지는 경우를 살펴보자

{1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1}

// i[0]
1, 12, 123

// i[1]
2, 23

// i[2]
3, 32, 321

// i[3]
2, 21

// i[4]
1

// i[5]
1, 12, 123

// i[6]
2, 23

...

 

각 시작점을 기준으로 숫자들의 등장 여부를 기록해두면서

다음 숫자가 기존에 등장했던 숫자일 경우에는 중복된 숫자이기 때문에

이 시점을 브레이크 포인트로 잡고 현재 까지 연속된 부분 수열의 길이를

결과를 저장할 변수에 누적해서 더해주면 된다.

 

위에서도 언급했지만 이 때 결과를 저장할 변수를 long 타입으로 해야한다...

 

1 > 2 > 3 > 2(기존에 등장함)

 

즉, 1에서 출발 했을 때, 4번째 탐색한 숫자는 중복되기 때문에

저 시점에서 멈춘 후 현재 까지의 부분 수열인 {1, 2, 3}의 길이만큼

결과 변수에 합해준다.

2 > 3 > 2  (기존에 등장함)
3 > 2 > 1 > 1 (기존에 등장함)
2 > 1 > 1 (기존에 등장함)
1 > 1 (기존에 등장함)
1 > 2 > 3 > 2 (기존에 등장함)
2 > 3 > 2 (기존에 등장함)
...

 

이제 1로 시작하는 경우는 구했으니 시작 포인터를 1 증가 시킨 후에

위의 과정들을 반복하면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] arr = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		boolean[] isUsed = new boolean[100001];
		long sum = 0;
		int end = 0;

		for (int start = 0; start < n; start++) {
			while (end < n) {
				if (isUsed[arr[end]]) break;
				isUsed[arr[end++]] = true;
			}

			sum += end - start;
			isUsed[arr[start]] = false;
		}

		System.out.println(sum);
	}
}