[BaekJoon] 3066 브리징 시그널 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int portCount;
    static int[] portNumbers;

    static void input() {
        portCount = scanner.nextInt();
        portNumbers = new int[portCount];

        for (int idx = 0; idx < portCount; idx++) {
            portNumbers[idx] = scanner.nextInt();
        }
    }

    /*
     * 1번 포트부터 N번 포트까지, 즉 위에서 아래로 연결된 포트들 중 교차되지 않는 포트들을 골라서 최대 개수를 찾아야 한다
     * 결국 교차되지 않으려면 위에서부터 아래로 연결된 포트들의 번호가 증가해야 한다
     * 즉, 가장 긴 증가하는 부분 수열 문제로 바라볼 수 있다
     * 포트의 최대 개수가 40,000개이기 때문에 DP를 이용한 O(N^2) 풀이로 진행하기에는 시간초과가 발생할 수 있다
     * 그러므로 이분 탐색을 이용한 가장 긴 증가하는 부분 수열을 찾는 알고리즘으로 풀이를 진행한다
     */
    static void solution() {
        List<Integer> lis = new ArrayList<>();
        lis.add(0);

        for (int idx = 0; idx < portCount; idx++) {
            if (lis.get(lis.size() - 1) < portNumbers[idx]) {
                lis.add(portNumbers[idx]);
                continue;
            }

            int index = binarySearch(portNumbers[idx], lis);
            lis.set(index, portNumbers[idx]);
        }

        if (lis.size() - 1 == 0) {
            answer.append(1).append('\n');
            return;
        }
        answer.append(lis.size() - 1).append('\n');
    }

    static int binarySearch(int target, List<Integer> lis) {
        int left = 0;
        int right = lis.size() - 1;

        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) {
        int T = scanner.nextInt();
        for (int test = 0; test < T; test++) {
            input();
            solution();
        }

        System.out.print(answer);
    }

    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());
        }
    }
}