[알고리즘] 병사 배치하기

LIS 해결에 대한 개념을 갖고 접근하지 못하면 풀기 어렵다.

처음엔 stack에 넣었다 빼면서 해당 문제를 해결할 수 있을 것이라 생각했는데.. 아니였나보다.

방법이 있을 것 같긴한데 이 글을 쓰는 순간에도 될 것 같으면서도 잘 모르겠다.

결국 LIS(가장 긴 부분문자열) 해결 방법으로 해결하였다.

def solution(inputList):

    inputList.reverse()

    inc_arr = [sys.maxsize]*n

    for i in range(0,n):
        idx = bisect.bisect_left(inc_arr, inputList[i])
        #해당 인덱스에 값을 덮어씀 => 총 길이가 증가하지 않음
        inc_arr[idx] = inputList[i]
    print(len(inputList) - bisect.bisect_left(inc_arr, sys.maxsize))