백준 2568 전깃줄 - 2 Java [LIS]

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

2568번: 전깃줄 - 2

 

예제 입력 값이 2개씩(전봇대A, 전봇대B)인데 전봇대 A 기준으로 정렬하여

전봇대 B로 가장 긴 증가하는 수열을 만들고 인덱스 별 만들 수 있는 수열의 크기를 구하고

뒤에서부터 size가 처음 나온 위치를 제외한 모든 위치의 전봇대 A값을 출력한다

예제를 예시로 들어 전봇대 A를 기준으로 정렬을 하면

[1,8], [2,2], [3,9], [4,1], [6,4], [7,6], [9,7], [10,10] 이다

전봇대 B값만 따로 뽑아서 가장 긴 증가하는 수열을 만들고

인덱스 별 만들 수 있는 수열의 크기를 구하면

[ 8, 2, 9, 1, 4, 6, 7, 10 ] -> [ 0, 0, 1, 0, 1, 2, 3, 4 ] 가 되고,

뒤에서부터 탐색해서 4부터 1씩 줄여가면서

크기 값이 처음 나온 위치를 제외한 모든 위치를 선택하면

전봇대 B 기준으로 [ 8, 2, 9 ] 가 해당되고

전봇대 A 기준으로 바꾸면 [ 1, 2, 3 ]이 된다

예제 출력이랑 결과 값이 다르지만 결과값이 다양한 스페셜 저지문제라서 통과된다

 

// 입력 받아서 A 전봇대 값 기준으로 오름차순 정렬하기
// B 전봇대 값으로 가장 긴 증가 수열의 거리 배열 구하기
// 방문 배열 만들고 거리 배열을 뒤에서부터 탐색해서 처음으로 나오는 거리 배열 숫자 찾아서 방문 체크
// 방문 배열에서 false값만 찾아서 false인 A 전봇대 값 sb에 추가 후 출력

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st;
        int[][] arrs = new int[N][2];
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine().trim());
            arrs[n][0] = Integer.parseInt(st.nextToken());
            arrs[n][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arrs, Comparator.comparingInt(o1 -> o1[0]));
        int[] arr = Arrays.stream(arrs).mapToInt(o -> o[1]).toArray();
        int[] D = new int[N];
        int[] result = new int[N];
        D[0] = arr[0];
        int size = 1;
        for (int i = 1; i < N; i++) {
            int index = Arrays.binarySearch(D, 0, size, arr[i]);
            index = index >= 0 ? index : Math.abs(index) - 1;
            D[index] = arr[i];
            result[i] = index;
            if (index == size) size++;
        }

        int s = size-1, i = N-1;
        boolean[] vtd = new boolean[N];
        while (s >= 0) {
            if (result[i] == s) {
                vtd[i] = true;
                s--;
            }
            i--;
        }
        int count = 0;
        for (int n = 0; n < N; n++) {
            if (!vtd[n]) {
                count++;
                sb.append(arrs[n][0]).append("\n");
            }
        }
        System.out.println(count);
        if (count > 0) {
            sb.setLength(sb.length()-1);
            System.out.println(sb);
        }
    }
}

 

전깃줄이 1개이거나 제거할 전깃줄이 없는 경우를 고려하지 않아서 여러번 틀렸다

엣지 케이스를 잘 해결하자!