[백준]2550: 전구 - JAVA

[백준]2550: 전구 

2550번: 전구

풀이

🪑 LIS에 대한 개념이 없었더라면 LIS에 대해 이해부터 해야 하므로 어려웠을 문제이다. LIS를 알았다면 어렵지 않게 풀 수 있었을 문제였다.

 

 

🙋‍♀️ 우선 나는 LIS문제를 풀어본 적이 있었지만 오래전이라 기억이 나지 않았다. 그래서 LIS부터 다시 공부하였다!

 

🔹 LIS(Lowes Increasing Subsequence)

- 최장 증가 수열이라는 뜻이다.

- 예를 들면 [5, 6, 1, 2, 3] 이라는 배열이 있을때 [1, 2, 3]과 같이 해당 배열 내에서 제일 긴 증가하는 수열의 배열을 의미한다.

 

🔹 LIS는 어떻게 구할 수 있을까?

- 완전탐색: O(2^N)

- DP: O(N^2)

- 이분탐색: O(NlogN)

 

 

🔎 이전에는 DP로 풀어보았었다. 이번에는 이분탐색을 활용하여 푸는 방법을 알아보자.

 

🔹 LIS를 담은 리스트의 마지막 값과 수열의 현재 요소와 비교한다.

- 리스트의 마지막 요소가 현재 요소보다 작으면, 리스트의 마지막에 현재 요소를 추가한다.

- 리스트의 마지막 요소가 현재 요소보다 크면, 이분탐색을 진행하여 현재 요소가 들어갈 위치를 찾는다. 그리고 해당 위치의 값을 현재요소로 대체한다.

 

 

🔧 이제 문제를 풀어보자.

1. 스위치에서 전구로 뻗은 선이 서로 겹치지 않으려면 가리키는 전구의 순서가 증가하면된다. 그러므로 LIS를 활용한다.
2. 스위치의 번호를 입력받고, 이를 인덱스와 연결해 준다. (2번 스위치 - 0번 인덱스)
3. 전구를 입력받고, 이를 스위치의 인덱스와 연결해 준다. (4번 전구 - 4번 스위치 - 1번 인덱스)
4. LIS를 찾아준다.
5. 전구에 대한 스위치 정보를 찾아 출력한다. 출력할때는 오름차순으로 출력한다.

 

🔹 왜 LIS일까?

- 스위치에서 전구로 뻗은 선이 겹치지 않도록 누를 수 있는 최대의 숫자를 눌러야 하는 것과 같은 문제라고 볼 수 있다.

- 겹치지 않도록 누르기 위해 어떻게 해야할지 생각해보면 스위치가 가리키는 전구의 순서가 증가하면 된다.

- 즉, 0번 인덱스의 스위치가 2번 전구를 가리켰다면 그 다음 인덱스의 스위치는 2번보다 큰 전구를 가리키면 겹치지 않는다.

- 그러므로 LIS를 구해주어야 한다.

 

🔹 스위치의 번호를 입력받고, 인덱스와 연결해 준다.

- 문제에서 원하는 답은 스위치에 대한 정보이다. 하지만 LIS를 진행해야 하는 정보는 전구에 대해서이다.

- 이때 스위치의 번호는 순서와 상관없는 수로 되어있으므로 LIS를 수행하기 위해 인덱스와 연결해 준다.

- 이 정보를 사용하여 전구에서 LIS를 수행한다.

 

🔹 전구를 입력받고, 스위치와 연결해준다.

- 전구 번호와 스위치를 연결해 준다. 

- 만약 4번 전구를 입력받았다면 4번 전구에 해당하는 스위치의 인덱스인 1이 저장되어야 한다.

 

🔹 LIS를 찾아준다.

- 앞서 언급한 이분 탐색을 사용하였다.

- 이때 LIS에 저장되는 전구와 인덱스 정보를 저장한다. (다시 거꾸로 원래의 스위치 정보를 찾기 위함.)

 

🔹 전구에 대한 스위치 정보를 찾는다.

- 마지막으로 LIS를 수행한 전구의 인덱스와 LIS를 담은 list의 인덱스를 비교하며 거꾸로 원래의 스위치에 대한 정보를 찾아간다.

- 해당 인덱스를 가진 전구를 찾는 과정이다.

- 만약 현재 전구가 1번 전구라면 원래 1번 전구에 해당하는 스위치는 4번 스위치 이므로 4로 변경해 준다.

- 변경된 list를 오름차순하여 출력한다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n;
    static List<Integer> list = new ArrayList<>(); //LIS를 담을 리스트
    static Node[] node;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        
        Map<Integer, Integer> map = new HashMap<>();
        int[] origin_sw = new int[n];
        for(int i = 0; i < n; i++) { 
            int sw = scan.nextInt();
            origin_sw[i] = sw;
            map.put(sw, i);
        } 
 
        int[] bulb = new int[n];
        for(int i = 0; i < n; i++) { 
            bulb[i] = map.get(scan.nextInt());
        } 
 
        node = new Node[n];
        for(int i = 0; i < n; i++) { 
            if(list.size() == 0 || list.get(list.size() - 1) < bulb[i]) {
                list.add(bulb[i]);
                node[i] = new Node(bulb[i], list.size() - 1); // sw와 연결된 전구의 LIS위치
            } else {
                int idx = binarySearch(bulb[i]);
                list.set(idx, bulb[i]);
                node[i] = new Node(bulb[i], idx);
            }
        } 
 
        int idx = list.size() - 1;
        for(int i = n - 1; i >= 0; i--) {
            if(node[i].idx == idx) {
                list.set(idx--, origin_sw[node[i].num]);
            }
        }
        System.out.println(list.size());
 
        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < list.size(); i++) {
            sb.append(list.get(i) + " ");
        }
        System.out.println(sb.toString());
    }
 
    public static int binarySearch(int num) {
        int l = 0;
        int r = list.size() - 1;
        
        while(l <= r) {
            int m = (l + r) / 2;
 
            if(list.get(m) < num) {
                l = m + 1;
            } else{
                r = m - 1;
            }
        }
        return l;
    }
 
    public static class Node {
        int num;
        int idx;
 
        public Node(int num, int idx) {
            this.num = num;
            this.idx = idx;
        }
    }
}

 

 

REFERENCE

https://lotuslee.tistory.com/17?category=962720