728x90
[Gold II] 가장 긴 증가하는 부분 수열 3 - 12738
성능 요약
메모리: 181184 KB, 시간: 636 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,000,000,000 ≤ Ai ≤ 1,000,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
이분 탐색을 활용하여 가장 긴 증가하는 부분 수열을 찾는다.
배열의 처음 값을 list에 추가한 후, 다음 배열의 수를 확인하며 위치를 찾는다.
먼저 list의 마지막 값보다 배열의 값이 클 경우 증가하는 부분 수열이 성립하기 때문에 list에 추가한다.
아닌 경우에는 list에 들어갈 위치를 찾아 넣는다.
list에 들어갈 위치를 찾을 때 이분 탐색을 활용한다.
해당 값이 들어갈 위치는 lower bound를 활용하였다. 해당 값보다 같거나 큰 값을 찾은 후 그 위치에 값을 넣어줘야 한다.
수열의 index에서 가능한 값 중 가장 작은 값을 삽입해야 가장 긴 증가하는 부분 수열을 찾을 수 있기 때문이다.
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 int N;
static List<Integer> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
list = new ArrayList<>();
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 추가하기
list.add(arr[0]);
for (int i = 1; i < N; i++) {
if (arr[i] > list.get(list.size() - 1))
list.add(arr[i]);
else {
binarySearch(i, arr);
}
}
System.out.println(list.size());
}
static void binarySearch(int i, int[] arr) {
int start = 0;
int end = list.size()-1;
// 들어갈 위치 찾기
while (start < end) {
int mid = (start + end) / 2;
if (arr[i] <= list.get(mid))
end = mid;
else {
start = mid + 1;
}
}
list.set(start, arr[i]);
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 15684 - 사다리 조작 (자바 Java) (0) | 2023.02.05 |
---|---|
[백준] 1744 - 수 묶기 (자바 Java) (0) | 2023.01.26 |
[백준] 2193 - 이친수 (자바 Java) (0) | 2023.01.21 |
[백준] 17182 - 우주 탐사선 (자바 Java) (0) | 2023.01.13 |
[백준] 15591 - MooTube (Silver) (자바 Java) (0) | 2023.01.11 |