[BaekJoon] 2352 반도체 설계 (Java)

1.  문제 링크

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

2.  문제

요약

• 반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있습니다.
• n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 40,000보다 작거나 같은 정수 n이 주어지고 두 번째 줄에 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, ..., n번 포트와 연결되어야 하는 포트 번호가 주어집니다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정합니다.
• 출력: 첫 번째 줄에 최대 연결 개수를 출력합니다.

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[] ports;

    static void input() {
        Reader scanner = new Reader();
        n = scanner.nextInt();
        ports = new int[n];

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

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

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

        System.out.println(LIS.size() - 1 == 0 ? 1 : LIS.size() - 1);
    }

    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.  접근

• 연결되어야 하는 포트 번호들을 ports라는 배열에 저장합니다.
• ports라는 집합에서 가장 긴 증가하는 부분 배열을 찾습니다
  • 가장 긴 증가하는 부분 배열의 원소들을 저장할 ArrayList LIS를 생성하고 0을 넣어 초기화합니다.
  • ports의 첫 번째 포트 번호부터 마지막 포트 번호까지 각 포트 번호를 확인하면서 LIS(가장 긴 증가하는 부분 배열)를 찾습니다.
    • 만약 LIS의 마지막 원소가 현재 포트 번호보다 작다면 LIS에 현재 포트 번호를 넣습니다.
    • 만약 LIS의 마지막 원소가 현재 포트번호보다 크거나 같다면 이분탐색을 통해 LIS에서의 적절한 위치를 찾아 해당 위치의 원소와 현재 포트 번호를 변경합니다.
      • 포트 번호를 바꿔주는 이유는 이후에 LIS에 포함되어야 할 포트 번호들이 존재할 수 있는데 이 포트 번호들이 현재 LIS에 있는 큰 번호들 때문에 들어오지 못하면 안되므로 바꿔줍니다.
• 모든 포트 번호를 확인한 후에 (LIS의 길이 - 1)이 답이 됩니다. 만약 이 값이 0이라면 LIS의 최소 단위인 1이 답이 됩니다.