문제 접근
가장 긴 증가하는 부분 수열1에서 N 조건이 크게 증가한 문제입니다.
N이 10**6이므로 시간복잡도 N^2의 경우 꿈도 꿀 수 없습니다.
사실 처음엔 기존에 풀었던 스카이라인 문제처럼 스택을 이용해야 하나? 라는 생각으로 접근했는 데, 위치 정보(특히 가장 최근의 정보)를 사용할만한 그렇다할 이유가 없었습니다.
그래서,, 알고리즘 분류라는 힌트를 봤더니 이분탐색을 사용해야 한다고 하더군요.
N*logN 풀이 인것은 알고 있었습니다만, 이걸 바탕으로 이분 탐색이라는 풀이 방법을 생각해내진 못했습니다.
각설하고, 이분탐색을 어떻게 이용해야 할까?
저 같은 경우 풀이를 할 때, 극단적인 케이스에서 풀이 방법을 도출하는 걸 좋아하는 데 이번 문제의 경우
10 20 1 2 3 30 이라는 케이스를 생각해 봤습니다.
10 20 으로 착실하게 쌓아나가다가, 갑작스럽게 1이 들어옵니다. 이 경우가 굉장히 곤란한 데, 1이라는 정보를 어딘가에 저장하긴 해야합니다.
이후에 나올 수들이 2~10까지는 1에 쌓일 수 있고, 11~20의 경우, 앞서 나온 10이나 1 둘다 쌓을 수 있기 때문입니다.
근데 이때 의문이 듭니다. 만약 이 바로 뒤 숫자가 11이면 10, 1에 둘다 쌓일 수 있고 (10->11), (1->11) 모두 길이가 2가 나오는 데 굳이굳이 앞서나온 10이라는 정보를 저장할 필요가 있을까?
1은 이 뒤에 나올 2~20을 모두 커버할 수 있으나, 10은 2~10을 커버할 수 없습니다. 그러니깐 10이라는 정보는 버려도 됩니다. 1이 10의 상위 호환이라고 볼 수 있죠.
하지만 20을 버릴 순 없습니다. 왜냐면 이미 증가 수열 길이가 2기 때문에 (10->20), 21 이상의 수를 쌓아서 길이 3(!)을 만들 수 있습니다. 이는 1이 커버할 수 없는 행위입니다.
그럼 이러한 일련의 사고과정에서 증가 수열 길이에 초점이 맞춰야 합니다. 10은 죽고 20은 살아 남았던 이유가 여기에 있기 때문입니다.
마침 N도 10**6이기에 Int 배열 백만개를 만들어도 4byte*10**6= 고작 4mb 밖에 안됩니다. (생각보다 공간복잡도가 더 널널하네요)
[0,0,0,0, . ..... 0] 백만개
10 20 1 2 3 30
이제 이 숫자에 맞춰 차례대로 배열을 채워 나가 봅시다.
1번 숫자 10 -> [0,10,0 ...]
2번 숫자 20 -> [0,10,20, . ...]
3번 숫자 1 -> 이건 위에 쌓을 수 없음. 20>1 ? 그럼 1은 어디에 들어갈지 어떻게 알지?
이때 이분 탐색을 이용합니다. 정렬된 배열 중 1보다 작은 수들 중에서 가장 큰 수의 바로 오른 칸에 넣으면 됩니다.
(생각의 흐름이 여기까지 왔서 이분 탐색을 사용했을 때, 이건 풀었다고 생각했습니다.)
여기의 경우 0번째의 0<1이기에 1은 그 옆 10 대신 들어갑니다. 상위 호환이 자리를 갈아끼운거죠
-> [0,1,20,0,,,,]
4번 숫자 2 -> [ 0,1, 2, 0,,,,] (앞서 말한 이분 탐색을 또 사용합니다. 즉 (1->2)는 (10->20)의 상위 호환입니다.)
5번 숫자 3 -> [ 0, 1, 2, 3, 0,,,,]
6번 숫자 30 -> [ 0, 1, 2, 3, 30, 0,,,,]
즉 이때 0이 아닌 숫자 중 가장 큰 30이 들어있는 위치 4가 정답이 됩니다.
풀이 코드
MAX=10**6
N=int(input())
A=list(map(int,input().split()))
increase=[0]*(MAX+1)
now_max=0
def find_small(start,end,insert):
while True:
if start>end:
ans=end
break
mid=(start+end)//2
if increase[mid]>=insert:
end=mid-1
else:
start=mid+1
return ans
for i in range(N):
Almost=find_small(0,now_max,A[i])
if increase[Almost+1]==0:
now_max+=1
increase[Almost+1]=A[i]
print(now_max)
find_small 함수를 통해서 리스트에서 삽입할 수보다 작은 수 중 가장 큰 수의 인덱스를 반환해줍니다.
이때 리스트 자체가 정렬이 된 형태이기에, 이진 탐색을 사용해서 위치를 훨씬 빠르게 찾을 수 있기에 시간 초과를 탈출할 수 있습니다.
반환받은 인덱스 1칸 위는 무조건 현재 삽입할 수보다 작거나 같기 때문에 정렬이 깨질 부담 갖지 않아도 됩니다.
만약 index+1이 0으로 아직 닿지 못했던 위치라면 최대값을 하나 늘리고, 그 수를 집어넣습니다.
최종적으로 now_max(최대값)를 출력해주면 정답입니다.
느낀점
증가하는 부분 수열에서의 특이성
기존에 쌓아갔던 수열에서 작은 수들은 의미가 없어집니다. (이 상위 문제인 증가하는 수열5에서는 이 기록들도 이용을 합니다만)
더 상위 호환으로 차차 수열을 바꿔나간다는 생각의 흐름이 어려웠던 느낌.
다만 N*logN이라는 시간복잡도가 강제되는 상황 (N=1000000)속에서 log라는 힌트에 맞춰 이진탐색을 고려하고 다시 여기에 상황을 대입하면 실전에서 풀이가 가능할 것 같습니다.
이진 탐색에서의 종료 조건
기존에 이진 탐색은 찾으려는 수의 위치를 찾을 때나, 힙, 세그먼트 트리와 같이 이진 탐색 친화적인 자료구조를 이용해 푼 경우가 많았는데,
이번 종료 조건은 삽입하려는 수보다 작은 수들 중 가장 큰 수의 위치였습니다. 이 과정에서 Start, End, Middle을 고려해 정확한 종료 조건을 만드는 게 중요했고 까다로운 포인트 였는 데, 앞으로도 다양한 이진 탐색 변환에 대한 연습이 필요해 보입니다.
