백준 11053번 - 가장 긴 증가하는 부분 수열(LIS)

 

가장 긴 증가하는 수열을 찾는 문제이다. A[0] 부터 A[N-1]까지 돌면서 증가하는 각각의 수열들을 모두 구하고 비교하면 시간 복잡도가 O(n^2)이기 때문에 백준에서는 오답일 것이다. 각 원소마다 비교하는 것은 맞지만 비교할 때 모든 원소를 비교하는 것이 아니라, 이전에 증가했던 수들에 대해서만 비교를 해주면 문제가 풀릴 것이다.

 

A = 10 3 4 5 1 2 3 4 이라고 할 때, index의 편의성을 위해서 A[0]에 0을 넣어줬다. 즉, A = 0 10 3 4 5 1 2 3 4이다.

기본 컨셉은 각 원소들을 돌면서 이전의 수보다 크면 cnt를 증가시켜서 몇번째에 위치하는 수인지를 구하는 것이다.

예를 들면 10보다 작은 수는 0 하나이기 때문에, 10의 max_cnt는 1이고, 3의 max_cnt도 1이지만, 4의 max_cnt는 2이다.

10과 3의 max_cnt가 같기 때문에, A_max에 append 됐던 10이 3으로 대체된다. 그러면, 5까지 돌았을 때 A_max는

0,3,4,5이다. A의 끝까지 대체를 반복하면 A_max는 0 1 2 3 4일 것이다. 하지만 만약 A가 10 3 4 5 1 2 까지였다면, A_max는 0 1 2 5 일 것이다. 그러므로 A_max가 꼭 증가하는 부분 수열을 저장한다고는 할 수 없다.

 

이 문제에서는 길이만 구하기 때문에, A_max 에 따라 max_cnt에 길이가 저장되기 때문에, max_cnt를 pop() 해주면 LIS를 구할 수 있다.

 

##변수 선언 부분##
A = []
max_cnt = []
A_max = []
max_num = 0
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split()]
    A.insert(0,0) #index의 편리성을 위해서 0을 넣어준다.
    max_cnt = [0] #초기값 설정
    A_max = [0]
    for i in range(1,N+1): 
        max_num = 0
        for j in range(len(A_max)):
            if A[i] > A_max[j]: #자신보다 작은 수를 세준다.
                max_num += 1
            if max_num == max_cnt[j]: #만약 자신보다 작은 수의 개수가 같고
                if A[i] < A_max[j]: #이미 저장되어있는 값보다 작다면 
                    A_max[j] = A[i] #저장되어있는 값을 갱신해준다.
                    max_num = 0 #초기화
                    break 
                else:
                    max_num = -1 #자신보다 크거나 같으면 더 순회할 이유가 없기 때문에 탈출
                    break
        if max_num > 0: #자신이 제일 큰 수일 경우에
            A_max.append(A[i]) #값을 append해준다.
            max_cnt.append(max_num) 
    print(max_cnt.pop())