P.2568 전깃줄 - 2

코드

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

public class Main {

    static int n;
    static ArrayList<ElectricWire> electricWires = new ArrayList<>();
    static ArrayList<Integer> lis = new ArrayList<>();
    static int[] idxes;

    static public class ElectricWire {
        int a;
        int b;

        public ElectricWire(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

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

        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            electricWires.add(new ElectricWire(line[0], line[1]));
        }
        Collections.sort(electricWires, Comparator.comparing(o -> o.a));
        idxes = new int[n];

        lis.add(electricWires.get(0).b);
        for (int i = 1; i < n; i++) {
            if (lis.get(lis.size() - 1) < electricWires.get(i).b) {
                lis.add(electricWires.get(i).b);
                idxes[i] = lis.size() - 1;
            } else idxes[i] = binarySearch(electricWires.get(i).b);
        }

        int cur = lis.size() - 1;
        ArrayList<Integer> removeItems = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            if (idxes[i] == cur) cur--;
            else removeItems.add(electricWires.get(i).a);
        }
        Collections.sort(removeItems, Comparator.comparing(o -> o));

        bw.write(removeItems.size() + "\n");
        for (Integer removeItem : removeItems) {
            bw.write(removeItem + "\n");
        }
        bw.flush();
    }

    private static int binarySearch(Integer value) {
        int start = 0, end = lis.size() - 1;

        while (start < end) {
            int mid = (start + end) / 2;

            if (lis.get(mid) < value) start = mid + 1;
            else end = mid;
        }
        lis.set(end, value);

        return end;
    }
}

코드 설명

초기 접근은 b에서 전깃줄이 정렬되어있을 때 교차하지 않는다는 것이었다.

a를 기준으로 b의 전깃줄을 정렬했을 때, 1 2 3 4와 같은 경우로 정렬이 된다면 교차하지 않지만

1 3 2 4로 될 경우 교차하는 부분이 발생한다.

 

LIS(최장증가수열)까지 도달하진 못했는데 문제를 많이 봐야할 것 같다.

LIS임을 판단하는 핵심 증거는 두 가지다.

1. 두 선이 서로 교차하지 않도록 하라는 요청을 받는 경우, 시퀀스 기반 문제이다.
2. 최대 순서 수열을 유지하고 최소 순서를 버리는 구조는 LIS에 해당한다.

LIS의 알고리즘은 다음 글에 있다.

2023.09.22 - [코딩테스트/백준] - P.14003 가장 긴 증가하는 부분 수열 5

P.14003 가장 긴 증가하는 부분 수열 5

 

최장 증가 수열에 해당하지 않는 원소들은 ArrayList로 모아 정렬하는 과정을 거쳐 답을 도출해냈다.

int cur = lis.size() - 1;
ArrayList<Integer> removeItems = new ArrayList<>();
for (int i = n - 1; i >= 0; i--) {
    if (idxes[i] == cur) cur--;
    else removeItems.add(electricWires.get(i).a);
}
Collections.sort(removeItems, Comparator.comparing(o -> o));