[백준] 2550. 전구

문제 링크

[백준] 2550. 전구

풀이 과정

최장 증가 부분 수열(LIS) 문제로, 최장 증가 부분 수열의 길이와 그 수열 자체를 출력해야 하는 문제입니다. 서로 교차하지 않는 최대한 많은 전선을 그려야 한다는 점에서 [백준] 2565. 전깃줄 문제와 유사합니다.

int[] switches = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] bulbs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
pairs = new Pair[N];

for (int i = 0; i < N; i++) {
    int target = switches[i];

    for (int j = 0; j < N; j++) {
        if (bulbs[j] == target) {
            pairs[i] = new Pair(j, target);
            break;
        }
    }
}

입력은 문제에 주어진 그림상 위에서 아래로의 스위치 및 전구 번호들이 배열로 주어집니다. 먼저, 배열 switches 와 bulbs 에 스위치와 전구 각각의 정보들을 담습니다. 이후, pairs 라는 배열에 목적지 인덱스와 스위치 번호를 담습니다.

예를 들어, 문제에서 주어진 입력 예제로 위와 같은 pairs 배열을 완성시킬 수 있습니다. 예를 들어, pairs[0] = { 4, 2 }를 통해, 0번 인덱스의 스위치는 4번 인덱스의 전구로 연결되며, 스위치 번호는 2라는 정보를 담고 있습니다.

dp[0] = pairs[0].first;
tracking[0] = new Pair(idx, pairs[0].second);

for (int i = 1; i < N; i++) {
    if (dp[idx] < pairs[i].first) {
        dp[++idx] = pairs[i].first;
        tracking[i] = new Pair(idx, pairs[i].second);
    } else {
        int target = binarySearch(idx, pairs[i].first);
        dp[target] = pairs[i].first;
        tracking[i] = new Pair(target, pairs[i].second);
    }
}

PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));

for (int i = N - 1; i >= 0; i--) {
    if (tracking[i].first == idx) {
        pq.add(tracking[i].second);
        idx--;
    }
}

이제 이분 탐색을 통해 최장 증가 부분 수열을 구한 후, 역추적을 통해 최장 증가 부분 수열 그 자체를 구합니다. 배열 dp에는 최장 증가 부분 수열 각 요소가 담기며, 배열 tracking에는 역추적을 위한 정보가 각 요소로 저장됩니다.

이분 탐색을 이용한 LIS 구현 및 역추적 방법은 [알고리즘 정리] 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)에 작성해 두었습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static Pair[] pairs;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] switches = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] bulbs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        pairs = new Pair[N];
        dp = new int[N];
        Pair[] tracking = new Pair[N];
        int idx = 0;
        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < N; i++) {
            int target = switches[i];

            for (int j = 0; j < N; j++) {
                if (bulbs[j] == target) {
                    pairs[i] = new Pair(j, target);
                    break;
                }
            }
        }

        dp[0] = pairs[0].first;
        tracking[0] = new Pair(idx, pairs[0].second);

        for (int i = 1; i < N; i++) {
            if (dp[idx] < pairs[i].first) {
                dp[++idx] = pairs[i].first;
                tracking[i] = new Pair(idx, pairs[i].second);
            } else {
                int target = binarySearch(idx, pairs[i].first);
                dp[target] = pairs[i].first;
                tracking[i] = new Pair(target, pairs[i].second);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));

        for (int i = N - 1; i >= 0; i--) {
            if (tracking[i].first == idx) {
                pq.add(tracking[i].second);
                idx--;
            }
        }

        answer.append(pq.size());
        answer.append("\n");

        while (!pq.isEmpty()) {
            answer.append(pq.poll());
            answer.append(" ");
        }

        System.out.println(answer);
    }

    static int binarySearch(int high, int target) {
        int low = 0;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (dp[mid] < target) low = mid + 1;
            else high = mid - 1;
        }

        return low;
    }

    static class Pair {
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}