[오답노트] BOJ : 13144 List of Unique Numbers - JAVA

박철민·2022년 11월 29일

오답노트

목록 보기

3/14

BOJ 13144 List of Unique Numbers

난이도 : 골드 4
풀이 날짜 : 22-12-18
출처 : https://www.acmicpc.net/problem/13144

풀이

수열을 앞에서 부터 하나하나 봤을 때 연속적일 경우와 이미 있는 애가 있는지를 봐야한다.

예를 들어 아래에 입력 예제를 보면 된다.

1이 처음 입력이 들어오면 이걸로 표현할 수 있는 경우의 수는 1이다.
그 다음에 2가 들어온다. 2는 1과 다르기 때문에 연속으로 표현 할 수 있다.

1 / 2 / 1,2 로 표현이 가능하다.

이 뒤에 3이 들어오게 되면 3은 1, 2와 다르기 때문에 연속으로 표현 할 수 있다.

1 / 2 / 1, 2 / 2, 3 / 1, 2 ,3 / 3

3이 들어옴으로서 3 / 2, 3 / 1, 2, 3 이 추가적으로 표현이 된다.

즉 연속된 수열에서 중복되지 않은 수가 추가가 되면 연속 수열의 길이 만큼 표현 가능한 경우가 추가가 된다.

그렇다면 만약

1 2 3 1이라면 어떻게 될까?
연속된 수가 아니기 때문에 1, 2, 3, 1이 연속이 될 때까지 앞을 버려주면 된다.
2, 3, 1이 이제 연속된 수기 때문에 길이 만큼 더해주면 된다.

1
1 2
1 2 3
2 3 1

1 2 3 1은 표현 가능한 수가 1 + 2 + 3 + 3 = 9이 된다.

1 2 3 2이라면?
1
1 2
1 2 3
3 2

1 + 2 + 3 + 2 = 8이 된다.

투포인터

결국 연속된 수열의 맨 앞을 가르키는 포인터와 맨 끝을 가르키는 포인터를 이용해서 길이를 계속 더해주는 방식으로 문제를 해결 할 수 있을 것 같다.

0부터 시작해서 연속될때 까지 하나씩 수열을 늘려가면서 그 길이를 더해줍니다.
그러다가 연속이 되지 않게 되면은 연속이 될 때까지 앞에를 비워줍니다.
연속이 되었다면 연속이 된 수의 길이를 더해줍니다.

끝 부분 포인터가 수열의 끝에 닿으면 모든 경우의 수가 계산이 됩니다!

코드

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

public class No13144 {
	public static void main(String[] args) throws IOException {
		// 입력 시작
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());

		int[] arr = new int[N];
		HashSet<Integer> set = new HashSet<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		// 입력 끝
		
		// 현재 나온 숫자가 몇개 나왔는지를 세주는 배열
		int[] count = new int[100001];
		
		// 경우의 수
		// 1부터 100,000까지의 피보나치가 들어갈 수도 있다.
		// 100_001 * 100_000 / 2 = 5000050000
		long sum = 0;

		// 시작 포인터 : s
		// 끝 포인터 : e
		for(int s=0, e=0; e<N; e++) {
			// e번째의 숫자를 올려줍니다.
			count[arr[e]]++;
			
			// 새로온 수가 이미 있는 애라 갯수가 2가 되었다면 앞에를 이동해줘야 합니다.
			if(count[arr[e]]==2) {
				// count[arr[e]]의 카운트가 1일 될 때까지
				while(count[arr[e]] == 2) {
					// 앞어 것들을 하나하나 빼줍니다.
					count[arr[s]]--;
					s++;
				}
			}
			// 수열의 길이를 sum에 더해줍니다.
			sum += (e - s + 1);
		}
		// sum을 표현
		System.out.println(sum);
	}
}