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

문제

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

 

 

입출력

6
10 20 10 30 20 50

4

 

---

아이디어

 

- 증가하는 부분 수열을 유지하는 배열 LIS + 이분탐색

1) A[i] 가 LIS 배열의 마지막 원소보다 크면 추가

2) 아니라면 이분 탐색을 통해 교체할 위치를 찾아 값 교체 

 

- 이분 탐색으로 O(NlogN) 내에 해결하기

// 개선이 필요한 로직
for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

 

- Collections.binarySearch()

 

• 리스트에 값이 존재하면 → 해당 값의 인덱스(index)를 반환
• 리스트에 값이 존재하지 않으면 → 값이 들어갈 "삽입 위치(insertion point)" 를 -(insertion point) - 1로 반환

 

 

코드 

• 값이 없다면, - (들어갈 위치 - 1) 반환

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

		System.out.println(lisLength(arr));
	}

	public static int lisLength(int[] arr) {
		List<Integer> lis = new ArrayList<>();

		for (int num : arr) {
			int pos = Collections.binarySearch(lis, num); // 값이 없다면, -(들어갈 위치 - 1) 반환
			if (pos < 0)
				pos = -(pos + 1); // 이분 탐색 위치 변환

			if (pos == lis.size()) {
				lis.add(num); // 새로 추가
			} else {
				lis.set(pos, num); // 값 교체
			}
		}
		return lis.size(); // LIS 길이 반환
	}
}