[BaekJoon] 1365 꼬인 전깃줄 (Java)

1.  문제 링크

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

2.  문제

요약

• 공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 두 줄로 늘어서 있는데 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있습니다.
• 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있는데, 꼬여있는 전깃줄은 화제를 유발할 가능성이 있어 시장 임한수는 꼬여있는 전깃줄 중 몇 개를 적절히 잘라 내어 문제를 해결하고자 합니다.
• 이미 설치해놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여있는 전선이 하나도 없게 만드려고 합니다.
• 유스타운 시의 시장 임한수가 잘라내야 할 전선의 최소 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 전봇대의 개수 N이 주어지고 두 번째 줄에 N보다 작거나 같은 자연수가 N개 주어집니다. 두 번째 줄의 i번째에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타냅니다.
• 출력: 첫 번째 줄에 전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는지를 출력합니다.

3.  소스코드

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

public class Main {
    static int N;
    static int[] pairs;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        pairs = new int[N];

        for(int idx = 0; idx < N; idx++)
            pairs[idx] = scanner.nextInt();
    }

    static void solution() {
        ArrayList<Integer> LIS = new ArrayList<>();
        LIS.add(0);

        for(int idx = 0; idx < N; idx++) {
            if(LIS.get(LIS.size() - 1) < pairs[idx]) {
                LIS.add(pairs[idx]);
            } else {
                int index = binarySearch(1, LIS.size(), pairs[idx], LIS);
                LIS.set(index, pairs[idx]);
            }
        }

        int cuttedLine = N - (LIS.size() - 1);
        System.out.println(cuttedLine);
    }

    static int binarySearch(int left, int right, int target, ArrayList<Integer> LIS) {
        while(left < right) {
            int mid = (left + right) / 2;

            if(LIS.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 전선이 꼬여있지 않으려면 왼쪽의 더 낮은 번호의 전봇대에서는 더 높은 번호의 전봇대에서보다 더 낮은 번호의 오른쪽 전봇대와 연결되어야 합니다.
• 즉, 예를 들어 왼쪽의 1번째 전봇대는 2번째 전봇대보다 더 낮은 번호의 오른쪽 전봇대와 연결되어야 합니다.
• 그렇기 때문에 주어진 전선의 정보에서 증가하는 가장 긴 부분 수열(LIS)을 찾아낸 후 그것을 제외한 나머지 전선을 잘라내면 그것이 이 문제의 답이 될 것입니다.
• LIS의 길이를 구하기 위해 LIS라는 ArrayList를 생성하고 0을 넣어 초기화해줍니다.
• 주어진 오른쪽 전봇대 번호들을 하나씩 순회하면서 LIS의 길이를 구합니다.
  • 만약 LIS의 가장 마지막 원소보다 현재 전봇대 번호가 더 크다면 LIS에 넣습니다.
  • 만약 LIS의 가장 마지막 원소보다 현재 전봇대 번호가 같거나 더 작다면 이분 탐색을 통해 적절한 위치를 찾아 해당 위치에 현재 전봇대 번호를 넣어줍니다.
• 모두 순회한 후에 (LIS의 길이 - 1)이 LIS의 길이가 됩니다.
• 전봇대의 개수인 N에서 LIS의 길이를 빼면 잘라야하는 전선의 개수가 나오고 이 값이 답이 됩니다.