[JAVA] BOJ 백준 13144번 - List of Unique Numbers

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

13144번: List of Unique Numbers

---

2. 내가 푼 방법

메모리초과를 해결하지 못해서 다른 분의 코드를 이해한 후 풀었다.

같은 범위 내 속하는지 확인하는 boolean[] check 배열과 투포인터를 사용하여 문제를 해결했다.

 

연속한 n개 이상의 수를 뽑는 경우의 수 : n * (n+1) / 2

 

while 문의 조건을 end < N 을 기준으로 두고 싶었기 때문에 아래와 같은 시나리오를 가져가야 했다.

전체 만들 수 있는 경우의 수 - 같은 범위 내 동일한 값을 가지는 경우의 수

 

• 전체 범위에서 만들 수 있는 경우의 수

long result = (long)((long)N * (long)(N+1) / 2l);

result의 경우에는 Integer의 범위를 넘어가기 때문에 long으로 설정해 주었다.

 

• 같은 범위 내 동일한 값을 가지는 경우의 수

int start = 0;
int end = 0;
while (end < N) {
    if (check[arr[end]]) {
        check[arr[start]] = false;
        start++;

        result -= (long)(N - end);
    }
    else {
        check[arr[end]] = true;
        end++;
    }
}

같은 범위 내 arr[end] 값이 존재할 경우에는 start++를 해주고,

같은 범위 내 arr[end] 값이 존재하지 않을 경우에는 end++를 해준다.

이때 result에 같은 범위 내 동일한 값을 가지고 있는 경우의 수를 빼주어야 하므로 현재 묶음을 가질 수 있는 뒤에 있는 값들이 경우의 수가 된다. 따라서 N - end를 해주는 것이다.

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B13144.java

import java.util.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[] check = new boolean[100001];

        long result = (long)((long)N*(long)(N+1) / 2l);
        int start = 0;
        int end = 0;
        while (end < N) {
            if (check[arr[end]]) {
                check[arr[start]] = false;
                start++;

                result -= (long)(N - end);
            }
            else {
                check[arr[end]] = true;
                end++;
            }
        }

        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }
}

---

4. 결과 및 회고

카운팅하는 과정보다 전체에서 제외해 가는 과정이 더 이해가 쉬운 것 같다.

처음엔 생각해내지 못했는데, 다음번에 풀 땐 이러한 방법도 고민해 보도록 해야겠다.