[Gold II] 가장 긴 증가하는 부분 수열 2 - 12015
성능 요약
메모리: 322700 KB, 시간: 1716 ms
분류
이분 탐색(binary_search), 가장 긴 증가하는 부분 수열: O(n log n)(lis)
문제 설명
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
그냥 dp 문제로 생각했는데 시간 초과가 났다.
이분 탐색을 활용해서 해당 수가 위치할 수 있는 index를 찾아가며 추가해야 하는 문제였다.
https://jason9319.tistory.com/113
이 링크에서 풀이법을 참고하였다.
list의 마지막 원소가 현재 원소(num)보다 작다면, num을 수열에 추가할 수 있으니 list에 추가하고 cnt를 1 더해준다.
만약 작다면 lower_bound의 방법을 통해 num이 위치할 수 있는 곳을 찾는다. (lower_bound:num 이상의 값이 처음 나오는 index) 그리고 list의 값을 num으로 교체한다.
이 값을 교체해야하는 이유는 num이 위치할 index의 값은 num 이상이기 때문에, num은 해당 index에 위치할 수 있는 값 중 최소가 된다. 이후 입력될 값들이 num보다 크고 기존 index 값보다 작은 경우에 이를 num으로 갱신해주지 않으면 최장 증가 수열의 길이를 알아낼 수 없다.
(위 링크 참고)
이 과정을 반복하다보면 list의 길이(cnt)가 최장 증가 수열의 길이가 된다.
package BOJ.Gold.g2;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class BOJ_12015_LIS2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<Integer> list = new ArrayList<>();
int cnt = 1;
list.add(sc.nextInt());
for (int i = 1; i < N; i++) {
int num = sc.nextInt();
if (num > list.get(list.size() - 1)) {
list.add(num);
cnt++;
} else {
int idx = find(num, list);
list.set(idx, num);
}
}
System.out.println(cnt);
}
static int find(int num, List<Integer> list) {
int start = 0;
int end = list.size() - 1;
while (start < end) {
int mid = (start + end) / 2;
if (list.get(mid) >= num) {
end = mid;
} else
start = mid + 1;
}
return end;
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1987 - 알파벳 (자바 Java) (0) | 2022.10.28 |
---|---|
[백준] 17143 - 낚시왕 (자바 Java) (0) | 2022.10.26 |
[백준] 1520 - 내리막 길 (자바 Java) (0) | 2022.10.24 |
[백준] 11066 - 파일 합치기 (자바 Java) (0) | 2022.10.23 |
[백준] 7579 - 앱 (자바 Java) (0) | 2022.10.21 |