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

백준 바로가기

12015번: 가장 긴 증가하는 부분 수열 2

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

이분 탐색 마지막 문제입니다. 시험이 있어 참여하지 못한 주차에 스터디원들이 진행한 개념이 이분 탐색인데, 그 때 다루지 않은 문제를 제가 맡아 풀게 되었습니다. 이분 탐색은 시간 복잡도를 log2n으로 낮춰줍니다. 범위를 절반으로 나눠 타겟값이 들어있는 한쪽에서 탐색이 진행되기 때문이죠. 

이 문제 접근방식은 '해결하는 목적이 무엇인지 알고 접근하라.' 입니다. LIS 배열을 구현해내는 것이 아니라 길이(size)만 출력하면 된다는 것이 포인트입니다. 그래서 주어진 배열의 인자값들을 해답 리스트에 오름차순으로 추가해줍니다. 다만 리스트 size를 증가시키는 add는 리스트의 최대값보다 큰 수가 들어왔을 떄만 실행되고 작거나 같을 경우 이분 탐색을 돌면서 들어갈 수 있는 자리에 set을 실행시켜 인자값이 '대체'됩니다.

여기서 set은 중요한 역할을 합니다. size에 영향을 미치지 않고 오름차순에 유리한 구조로 리스트 인자값들을 변형시켜 나가기 때문이죠. 간략한 예를 들자면, LIST: {10, 30, 40, 50}가 만들어졌을 때 20, 21, 23, 24가 순서대로 인자값으로 들어오면 20~23까지는 30, 40, 50을 차례대로 대체하여 마지막 24가 들어왔을 떄 리스트는 {10, 20, 21, 23}로 변형돼있어 24가 add 될 여지를 만들어 줄 수 있는 것입니다.

코드

package baekJoon.week18;
 
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 LongestArr_12015 {
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int reps = Integer.parseInt(br.readLine());
        int[] inputNumbers = new int[reps];
        st = new StringTokenizer(br.readLine());
        //주어진 숫자 배열에 담기
        for (int i = 0; i < reps; i++) {
            inputNumbers[i] = Integer.parseInt(st.nextToken());
        }
 
        //LIS 리스트
        List<Integer> longestArr = new ArrayList<>();
        //첫 인자를 추가해 주기위해 리스트에 최소값을 넣어둠
        longestArr.add(Integer.MIN_VALUE);
        for (int i = 0; i < reps; i++) {
            //주어진 배열 인자값을 number 변수로 받음
            int number = inputNumbers[i];
            int end = longestArr.size() - 1;
            //number가 리스트 최대값보다 크면 add, 작거나 같으면 이분탐색
            if (number > longestArr.get(end)) {
                longestArr.add(number);
            } else {
                int left = 0;
                int right = end;
                while (left < right) {
                    int middle = (left + right) / 2;
                    if (longestArr.get(middle) < number) {
                        left = middle + 1;
                    } else {
                        right = middle;
                    }
                }
                //end 인자값 다음으로 작으면 number값으로 최대값 교체
                //중간값이 되면 순서가 관여되는데 교체하면 안되지 않나?
                //add가 아니라 대체하는 것이기 때문에 size엔 영향을 주지 않는다.
                //10 30 40 50 20 이라면, 20이 left = 1번째가 되므로 30을 대체하여도 사이즈는 40 그대로다.
                longestArr.set(left, number);
            }
        }
        System.out.println(longestArr.size() - 1);
    }
}