[BOJ] 13144 - List Of Unique Numbers (Java)

접근법

문제 유형이 투포인터라는 점과, 수열을 확인하며 각 수열마다 겹치는 원소를 확인하는 방법은 굉장히 비효율적이며, 시간초과가 날 것이라는 생각이 들어 다음과 같이 생각했다.

1. 각 자리에 있는 원소들에서부터 만들 수 있는 조건에 맞는 수열은 중복되는 원소가 나오기 전까지의 수열의 갯수이다.

• 예로 {1, 2, 3, 4, 3, 5, 6} 을 살펴보자.{1}, {1,2}, {1,2,3}, {1,2,3,4} 가 된다.
• 이 것은 수열 {1,2,3,4} 의 원소의 갯수와도 같다.
• 처음 원소인 1에서 만들 수 있는 조건에 맞는 수열은

1. 중복된 원소가 나오는 순간 순열의 처음부터 끝까지 움직이며 어느 위치에 해당 중복되는 원소가 있는지 확인한다.

2-1) 이 과정에서 중복된 원소가 아닌 원소에서도 조건에 맞는 수열들이 나오게 되므로 이 또한 계산에 넣어준다.

1. 마지막 원소에 끝점이 다다랐을 때 해당 수열의 모든 원소들은 모두 조건에 충족하는 원소들이므로 이 또한 계산한다.

---

코드

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

		StringTokenizer st;

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

		int[] numArr = new int[N];

		boolean[] checker = new boolean[N + 1];
		for (int i = 0; i < N; i++) {
			numArr[i] = Integer.parseInt(st.nextToken());

		}
		int start = 0;
		int end = 0;
		long sum = 0;

		while (end < N) {
			if (checker[numArr[end]]) { // 존재한다 ( 수열 안에 포함돼있다. )
				// TODO 얘는 여기서 이제 끝
				while (end > start) {
					sum += (end - start);
					checker[numArr[start]] = false; // 다음으로 넘어가기 전에 sum에 계산하고, start를 checklist에서 뺌
					if (numArr[end] == numArr[start]) {
						start++;
						break;
					}
					start++; // 다음
				}
			} else {
				checker[numArr[end++]] = true; // 체크하고 다음으로
			}
		}
		for (int i = 1; i <= (end - start); i++) {
			sum += i;
		}
		System.out.println(sum);

	}
}

결과

메모리	시간	언어
25544KB	292ms	Java