소스코드는 Github에서도 확인하실 수 있습니다.
풀이 🚀
수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
풀이 방법은 다음과 같다.
먼저, A의 크기 + 1만큼의 int 배열을 만든다. 그리고 인덱스를 0으로 지정해준다.
A로 부터 순서대로 읽어들이는 숫자를 number라고 해 보자.
1. array[index] < number 인 경우
index를 1 증가시키고 array의 마지막에 해당 숫자를 넣어준다.
2. array[index] > number 인 경우
예를 들자면, array = {0, 10, 20} 인 상황에서 number로 10이 들어온 경우와 같다.
이 경우에는 기존 array에서 10의 lowerbound를 찾아서 해당 자리를 10으로 대체해주면 된다.
lowerbound라는 것은 특정 K값보다 같거나 큰값이 처음 나오는 위치를 리턴해주는 것을 말한다. 따라서 위 경우에서 10의 lowerbound는 1이 된다.
또 다른 예를 들어보자면 array = {0, 10, 20, 30}인 상태에서 number로 20이 들어온 경우를 생각해보자.
lowerbound(20)은, 20보다 같거나 큰 값이 처음 나오는 위치이므로 array에서 20의 위치인 2가 된다.
따라서 number로 들어온 20은 array[2]를 대체하게 된다.
1과 2를 반복하면서 array를 만든 뒤, index를 출력해주면 가장 긴 증가하는 부분수열의 길이가 된다.
여기서 왜 lowerbound를 사용하는 걸까?
lowerbound 자리를 찾아 number로 들어온 값을 대체하게 되면, input으로 들어오는 예측할 수 없는 수들 중 더 작은 수가 나왔을 때 받아들일 수 있는 범위가 넓어진다. 즉, 가장 긴 증가하는 수열이 되기 위한 최적의 상태를 만들어나간다.
예를 들어, 10 20 18 19 30 이라고 생각해보자.
array에 {10, 20} 이 있는 경우, 18의 lowerbound index는 1이 되고, 그 자리를 대체하면 array는 {10, 18}이 된다.
이렇게 되면 마지막에 20이 자리하는 경우보다, 18이 자리했을 때 뒤로 받아들일 수 있는 수들의 범위가 더 넓어지게 됨으로써 19를 다음으로 받아들일 수 있게 된다.
소스코드 👩🏻💻
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int A = Integer.parseInt(bufferedReader.readLine());
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int[] array = new int[A];
int index = 0;
for (int i = 0; i < A; i++) {
final int number = Integer.parseInt(stringTokenizer.nextToken());
if (number > array[index]) {
array[++index] = number;
} else if (number < array[index]) {
final int lowerBound = lower_bound(number, array, index + 1);
if (lowerBound > index) {
array[++index] = number;
}
array[lowerBound] = number;
}
}
System.out.println(index);
}
private static int lower_bound(int number, int[] array, int size) {
int left = 1;
int right = size; // size
while (left < right) {
int mid = (left + right) / 2;
int now = array[mid];
if (number <= now) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
테스트 케이스 모음