[백준] 가장 긴 증가하는 부분 수열2 12015번 - Java

[백준] 가장 긴 증가하는 부분 수열2 12015번

나의 풀이

public class LongestIncreasingSubsequence {
    static Stack<Integer> result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] subsequence = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            subsequence[i] = Integer.parseInt(st.nextToken());
        }

        result = new Stack<>();
        result.add(0);
        for(int target : subsequence) {
            if(result.peek() < target) {
                result.add(target);
            } else {
                result.set(binarySearch(target, 0, result.size() - 1), target);
            }
        }

        System.out.println(result.size() - 1);
        //0 카운트 제거
    }

    static private int binarySearch(int target, int start, int end) {
        while(start <= end) {
            int mid = (start + end) / 2;
            if(result.get(mid) < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return start;
    }
}

• 순차적인 배열을 담을 result를 스택으로 생성하였다.
• 입력받은 숫자들을 subsequence 배열에 숫자로 변환하여 담아준다.
• 우선 스택에 아무것도 없으면 안되기도 하고, subsequence 값들과 비교하기 위해 가장 작은 정수인 0을 add해준다.
• subsequence 배열을 돌면서 result 스택에서 peek을 하여, 가장 마지막에 있는 정수와 비교하여 subsequence의 값이 더 크면 스택에 해당 정수를 추가해준다.
• 아니라면 이분 탐색을 통하여 인덱스를 추출하여 스택의 해당 인덱스의 값을 subsequence의 값으로 세팅 해준다.
  • 이분 탐색은 subsequence의 값을 result 스택 내부를 탐색한다. 때문에 target은 subsequence의 값, start는 0, end는 result의 사이즈 - 1을 해준다.
  • start가 end보다 커질 때 까지 반복을 한다.
  • mid 값을 구해주고, result의 mid 번 째 값이 타겟보다 작다면 start = mid + 1, 아니면 end = mid - 1 을 해준다.
  • 반복이 끝나면 start 인덱스를 반환한다.
• 위 과정을 통해 result의 세팅이 끝나게 되고, 비교를 하기 위해 0을 추가했었기 때문에 result사이즈에서 -1을 해준다.