[Boj_2550] 전구

📎 문제 링크

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

 

▸ 문제

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.

 

하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.

위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이 누르면 전선이 만나는 1번과 5번 전구는 켜지지 않지만 3번 전구는 켜지게 된다.

여러분이 할 일은 가장 많은 전구가 켜지도록 스위치를 누르는 것이다. 위 그림에서는 3번과 4번 그리고 5번 스위치를 누르는 경우와 1번과 3번 그리고 4번을 누르는 경우에 세 개의 전구가 켜지게 되고, 이 두 가지 경우가 가장 많은 전구가 켜지는 경우이다.

스위치의 번호순서와 전구의 번호순서가 주어질 때, 어떤 스위치를 누르면 가장 많은 전구가 켜지는지를 알아내는 프로그램을 작성하시오.

 

▸ 입력

첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.

 

▸ 출력

첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다. 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 3
• 🔔  문제 유형 : 다이나믹 프로그래밍, 가장 긴 증가하는 부분 수열: o(n log n)
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 전선이 겹치지 않도록 하면서 전구가 가장 많이 켜지도록 하는 경우를 구하는 문제이다.

두 전선이 겹치지 않기 위해서는 스위치가 가리키는 전구의 순서가 증가하면 된다. 그러므로 LIS를 활용한다.

 

전구의 인덱스 1, 3, 2, 4, 0에서 가장 긴 증가하는 부분 수열을 찾으면 된다.

즉, 가장 긴 증가하는 부분 수열은 1, 3, 4 또는 1, 2, 4가 될 것이고, 이 인덱스에 해당하는 전구의 번호인 4, 5, 3 또는 4, 1, 3 중 하나를 오름차순으로 출력해 주면 답이 된다.

 

먼저, HashMap<Integer, Integer>을 이용해 스위치의 번호와 인덱스를 저장한다.

 

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

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

 

이제, 이분 탐색을 활용해 전구의 인덱스에 대해 LIS를 찾아준다.

이때, 원래의 스위치 정보를 찾기 위해 LIS에 저장되는 전구와 인덱스의 정보를 Node[] node에 저장한다.

 

마지막으로, LIS를 수행한 전구의 인덱스와 list의 인덱스를 비교하며 전구에 대한 스위치 정보를 찾는다.

만약, 현재 전구의 인덱스가 1번이라면 이에 해당하는 스위치는 4번 스위치므로 4로 변경한다.

변경된 list를 오름차순으로 정렬한 뒤 출력한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 19404KB
시간 : 204ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[] switches, lights;
    static ArrayList<Integer> list;
    static Node[] node;
    static public class Node {
        int num; int idx;
        public Node (int num, int idx) {
            this.num = num; this.idx = idx;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        HashMap<Integer, Integer> map = new HashMap<>(); // 스위치 번호, 인덱스

        StringTokenizer st = new StringTokenizer(br.readLine());
        switches = new int[n];
        for (int i = 0; i < n; i++) {
            switches[i] = Integer.parseInt(st.nextToken());
            map.put(switches[i], i);
        }
        lights = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lights[i] = map.get(Integer.parseInt(st.nextToken()));
        }

        getLis();

        StringBuilder sb = new StringBuilder();
        sb.append(list.size()).append("\n");

        Collections.sort(list);
        for (int i : list) {
            sb.append(i).append(" ");
        }

        System.out.println(sb.toString());
    }

    private static void getLis() {
        list = new ArrayList<>();
        node = new Node[n];
        int idx;
        for (int i = 0; i < n; i++) {
            if (list.size() == 0 || list.get(list.size()-1) < lights[i]) {
                list.add(lights[i]);
                node[i] = new Node(lights[i], list.size()-1);
            } else {
                idx = binarySearch(0, list.size()-1, lights[i]);
                list.set(idx, lights[i]);
                node[i] = new Node(lights[i], idx);
            }
        }

        idx = list.size()-1;
        for (int i = n-1; i >= 0; i--) {
            if (node[i].idx == idx) {
                list.set(idx--, switches[node[i].num]);
            }
        }
    }

    private static int binarySearch(int start, int end, int target) {
        int mid;
        while (start <= end) {
            mid = (start + end)/2;
            if (list.get(mid) < target) start = mid+1;
            else end = mid-1;
        }
        return start;
    }
}

 

해결 완료 ! 🔥