BOJ(백준 온라인 저지) 16566번 with 자바[JAVA]

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

---

문제는 단순해 보였다.

처음 문제를 읽자 마자 생각한 것은 다음과 같다.

1. 리스트에 민수가 뽑은 숫자들을 담는다.
2. 리스트를 정렬하고 철수가 보여주는 카드보다 큰 수의 숫자를 뽑는다.
3. 뽑은 숫자는 삭제하고 2번으로 돌아간다.

 

왜 리스트를 정렬하는가?

 

리스트를 정렬하지 않으면 철수가 보여주는 카드보다 큰 수들 중 가장 작은 수를 찾기 위해서는 선형탐색밖에 답이 없기 때문이다. 선형탐색의 시간 복잡도는 O(N) 이므로, 최대 4,000,000 x 10,000 = 40,000,000,000 의 연산이 필요하다. 대충 100,000,000 에 1초 이므로, 이는 반드시 시간초과가 발생한다.

 

하지만 정렬을 한다면 다르다. 정렬이 되어있는 자료구조에 대해서는 O(logN) 이 소모되는 이진탐색을 수행할 수 있고, 이를 통해서 찾고자 하는 수를 빠르게 찾을 수 있다.

 

왜 위 알고리즘은 틀렸는가?

 

리스트의 삽입, 삭제, 탐색에 대해 생각해보자. 해당 리스트가 LinkedList 인 경우, 삽입과 삭제에는 상수시간이 소모되지만, 내부적인 구조로 인해 탐색은 O(N) 이 소모된다.

 

ArrayList 인 경우, 삽입과 탐색에는 상수시간이 소모되지만, 삭제의 경우에는 O(N) 이 소모된다. 중간의 요소가 삭제되는 경우 빈 공간을 채우기 위해 뒤에 요소들을 당겨와야하기 때문이다.

 

LinkedList 를 사용할 거면 탐색의 시간을 줄여야 하고, ArrayList 를 사용할 거면 삭제의 시간을 줄여야 한다는 의미이다.

나는 이진 탐색을 사용하기 위해 ArrayList 를 사용하고, 삭제의 시간을 줄이는 방향으로 진행했다.

 

그렇다면...

 

삭제를 하면 안된다. 리스트에서 삭제를 하지 않고 해당 숫자를 사용하지 않을 방법을 생각해봤다.

 

첫 번째, boolean list 사용

 

2024.04.04 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 3 - Arrays for Search, Insert, Delete

자료구조 및 알고리즘 3 - Arrays for Search, Insert, Delete

Unpacked Sorted Array 에서 사용한 boolean list 를 생각했다.

사용하지 않은 숫자는 boolean true 로, 사용해버린 숫자는 boolean false 로 해서, 사용한 숫자와 사용하지 않은 숫자를 구분해주려 했다.

 

사용했다고 데이터를 삭제하는 것이 아닌 boolean 값만 바꿔주는 것 이기에 이진 탐색도 여전히 사용할 수 있다는 점에서 문제가 없어보였다.

 

하지만 결국 선형 탐색이다.

예를 들어보자:

 

입력:

10 7 5

2 5 3 7 8 4 9

1 1 1 1 1

 

출력:

2

3

4

5

7

 

이어야 한다. 이때 내부의 리스트를 살펴보자.

index	0	1	2	3	4	5	6
boolean	T	T	T	T	T	T	T
array	2	3	4	5	7	8	9

이때 1 이 입력으로 들어왔고, 1 보다 큰 수들 중 가장 작은 수인 2 를 이진 탐색으로 찾아서 출력해준다. 그리고 boolean 값을 false 로 바꿔준다. 그리고 또 1 이 입력으로 들어온다.

index	0	1	2	3	4	5	6
boolean	F	T	T	T	T	T	T
array	2	3	4	5	7	8	9

이진 탐색을 통해 1 보다 큰 수들 중 가장 작은 수인 2 를 찾았다. 하지만 2 의 boolean 값은 false 이므로 다음 수를 찾는다. 이때 문제가 발생한다. 이는 선형 탐색이다.

 

입력이 더 들어와서 마지막 1 이 입력으로 들어온 상황이라고 가정하자.

index	0	1	2	3	4	5	6
boolean	F	F	F	F	T	T	T
array	2	3	4	5	7	8	9

이진 탐색을 통해 1 보다 큰 수들 중 가장 작은 수인 2 를 찾았다. 하지만 2의 boolean 값은 false 이므로 다음 수를 찾는다. 다음 수는 3 이지만 boolean 값이 또 false 이므로, 다음 수를 찾는다. ,,, 이런 식으로 선형으로 탐색하게 되는 것이다.

 

하지만 이는 최악의 경우이다. 만약 중간 중간의 값이 비어있다면, 선형 탐색의 길이(?) 는 그리 길지 않을 것이다. 하지만 최악의 경우는 O(N) 임을 알아야 한다.

 

두 번째, Union-Find(or DisjointSet)

 

2024.06.09 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application

자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application

삭제를 할 필요가 없다. 묶어주면 된다.

 

리스트의 값들을 출력해야하는 값들을 기준으로 해서 묶어준다. 이해를 돕기 위해 위의 예시를 가져와보자:

 

첫 번째 1 이 입력으로 들어왔을 때, 이진 탐색을 통해 2 를 찾는다.

그리고 출력하는 값은 2 의 id 값이다. 초기의 id 는 자기자신이기 때문에 2 가 출력된다.

index	0	1	2	3	4	5	6
id	2	3	4	5	7	8	9
array	2	3	4	5	7	8	9

하지만 이후, 다음 값과 union 을 진행한다.

 

다시 말해, 2와 3을 묶어주는 것이다.  이렇게 하면 2와 3이 찾아졌을 때, 프로그램은 3을 출력할 것이다.

index	0	1	2	3	4	5	6
id	3	3	4	5	7	8	9
array	2	3	4	5	7	8	9

 

그렇다면 마지막 1 이 입력으로 들어왔을 때를 생각해보자,

프로그램 내부 리스트는 다음과 같을 것이다.

index	0	1	2	3	4	5	6
id	7	7	7	7	7	8	9
array	2	3	4	5	7	8	9

이때 1이 입력으로 들어오고, 이진 탐색을 통해 2 가 찾아지면, 2의 id 값인 7 을 출력해준다.

 

union-find 는 시간복잡도가 상수시간이므로 시간초과의 우려도 없다.

 

코드

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

public class Main {

    static int N;
    static int M;
    static int K;
    static int[] numList;
    static int[] disjointSet = new int[4000001];

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

        N = Integer.parseInt(st1.nextToken());
        M = Integer.parseInt(st1.nextToken());
        K = Integer.parseInt(st1.nextToken());

        numList = new int[M];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++){
            numList[i] = Integer.parseInt(st2.nextToken());
        }
        // 정렬
        Arrays.sort(numList);

        StringTokenizer st3 = new StringTokenizer(br.readLine());
        for(int i=0; i<K; i++){
            // 이진 탐색을 통해 주어진 수보다 큰 수들 중 가장 작은 수를 찾는다.
            int ans = findUpperThan(Integer.parseInt(st3.nextToken()));
            System.out.println(find(ans)); // 찾은 수의 id 값을 출력한다.
            // 이때 찾은 id 의 값이 민수가 가지고 있는 수들 중 가장 큰 수 였다면,
            // 그 다음 수를 union 해줄 수 없기 때문에, 그 경우가 아닌 경우에 대해서만 union 을 진행해준다.
            // 또한, 문제에서 민수가 카드를 내지 못하는 상황은 없다고 가정했으므로 문제가 되는 상황은 만들어지지 않는다.
            if(find(ans) != numList[M - 1])
                // 찾은 수와 그 다음 수를 union 해준다.
                // 그 다음 수는 엄밀히 정의하면 찾은 수의 id 값보다 큰 수들 중 가장 작은 수를 의미한다.
                // 따라서 findUpperThan 메서드를 다시 한 번 더 이용한다.
                union(find(ans), findUpperThan(find(ans)));
        }
    }

    private static int findUpperThan(int a) {
        int left = 0;
        int right = M - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(numList[mid] == a){
                // 해당 수를 찾았다면 그 다음 수를 return 해준다.
                return numList[mid + 1];
            }
            else if(numList[mid] > a){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        // 해당 수를 못 찾았다면, left 가 그 다음 수를 가르킨다.
        // 따라서 left 가 가르키는 수를 return 해준다.
        return numList[left];
    }

    public static int find(int a){
        if(disjointSet[a] == 0)
            return a;
        else{
            int id = find(disjointSet[a]);
            disjointSet[a] = id;
            return id;
        }
    }

    public static void union(int a, int b){
        if(find(a) == find(b))
            return;
        else{
            disjointSet[find(a)] = find(b);
            return;
        }
    }
}

정리

 

삭제의 시간복잡도를 줄이는 것, 이것이 핵심이었다.

문제의 특성에 맞게 여러가지 자료구조를 사용하는 능력이 필요로 했던 것 같다.