문제
풀이
DP로 푸는 방법도 있지만 그 경우는 리스트 전체를 훑는 반복문을 두 번 돌리는 O(N^2)의 복잡도를 가지기 때문에 이 문제의 조건에서 주어진 백만개의 리스트같은 경우는 시간복잡도가 터진다
원래 이 문제는 1.DP 2.이분탐색 두 가지 방법이 있는데, 여기서는 이분탐색을 사용해서 O(NlogN)시간 복잡도를 내야 풀 수 있다
사실 이 개념은 이해를 못해서 이 블로그를 참고했다
이 풀이의 기본적인 개념은 리스트를 1번만 보고 최장길이수열을 구하겠다는 것인데, 1번만 볼 때 우리가 알 수 있는 건 해당 리스트의 숫자들과 현재까지 구해진 최장 증가 부분 수열(Longest Increasing Subsequence)이다. 보통 LIS라고 부른다.
예를 들어 다음과 같은 입력값이 있다면
7
4 8 3 7 1 2 7
A라는 리스트에 데이터들을 받았다고 치면,
먼저 4를 시작으로 했을 때,
4는 가장 처음에 위치한 값이고 현재까지 우리가 구한 LIS는 아직까지 없으므로 LIS = [4]인 상태가 된다.
그 다음은 8인데, 현재 우리가 지금까지 구한 LIS는 [4]이고 8은 이 [4]의 가장 마지막 값 4보다 크다. 즉 뒤에 추가해주면 된다. 이제 LIS = [4, 8]이다.
최장 증가 부분 수열이기 때문에 당연히 오름차순으로 정렬되고 가장 마지막에 있는 값이 이 수열에서 가장 큰 값이다. 가장 큰 값보다 큰 값이다? 당연히 맨 뒤에 추가해주면 되는 것.
그 다음은 3, LIS는 [4, 8]
3은 8보다 작기 때문에 가장 뒤에 추가할 수는 없다. 하지만 4보다는 작다.
여기서 우리가 구하려는게 최장 길이 수열이라는 걸 다시 되새겨 봐야 한다. 결과적으로 가장 긴 길이를 가지는 수열을 구하기 위해서는 더 작은 숫자들이 앞에 있을 수록 유리하다. 즉, 맨 앞에 오는 숫자가 1일 때가 3일 때보다는 더 유리하게 된다. 3 1 2 와 같은 순서로 정렬되어 있을 때, LIS = [3] 으로 고정시켜놓게 되면 우리는 2를 만났을 때 이 값을 추가할 수 없다. 하지만 LIS = [1] 로 수정되면 2는 끝값인 1보다 크기 때문에 뒤에 추가할 수 있어 LIS = [1, 2]가 된다.
결국 구하려는 값이 최장 길이 수열이고, 그러기 위해서 우리는 계속해서 이 LIS의 값을 수정해나가면서 뒤에 올 숫자들이 추가될 수 있도록 앞의 숫자들을 줄여주는, 즉 수열의 길이가 늘어날 가능성을 마련해주는 과정을 반복하게 된다.
이 과정은 lower bound = 현재의 값보다 이상인 값이 가장 먼저 등장하는 위치를 찾아서 바꿀 수 있는데, 현재의 경우 3 이상인 값 = 4가 등장하게 되는 인덱스 0이 그 위치가 된다.
최종적으로 구한 LIS는 가장 긴 길이를 가지는 수열 문제에서 그 정답이 되지는 않지만 적어도 그 길이만큼은 정답이 될 수 있음
다음은 7, LIS = [3, 8]
7은 8보다 작아서 뒤에 추가될 수는 없지만, lower bound = 8이 등장하는 위치 = 1이므로 LIS = [3, 7]
다음은 1, LIS = [3, 7] 이므로 1은 3보다 작으므로 [1, 7]
다음은 2, LIS = [1, 2]
다음은 7, LIS = [1, 2, 7]
최종적으로 최장 길이를 가지게 되는 수열은 [1, 2, 7]로 정답은 3이 된다.
# 804ms
N = int(input())
A = list(map(int, input().split()))
def sol():
res = [A[0]]
for a in A[1:]:
if res[-1]<a:
res.append(a)
else:
res[bisect_left(res, a)] = a
return len(res)
print(sol())