[백준알고리즘] 2352번: 반도체 설계 -Python

[백준알고리즘] 2352번: 반도체 설계 -Python

https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다.

 

이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower bound를 이용한 방법을 사용하면 된다.

 

lower bound를 사용해서 추가할 수 있는 위치에 추가하는 방식은 O(NlogN) 정도의 시간 복잡도를 갖는다.

https://seungkwan.tistory.com/8

마지막 원소보다 삽입하려는 원소의 값이 작다면 삽입될 수 있는 위치에 적절히 교체하게 되면서 LIS를 만드는 것이 아닌 같은 길이의 부분 수열 중 가장 낮은 값을 유지하도록 하는 리스트를 만드는 것이라 보면 된다.. 말로만 보면 이해가 안 되기 때문에 위의 블로그를 참고하면 이해가 쉬울 것이다.

 

아무튼 lower bound로 삽입할 위치를 이분 탐색으로 찾기 때문에 시간 복잡도를 줄일 수 있게 된다. 이분 탐색을 사용하기 위해서 bisect 모듈의 bisect_left를 사용했다. 그리고 직접 이분 탐색 코드를 짜서도 시도해봤다.

from bisect import bisect_left

n = input()
dest = list(map(int, input().split()))
link = []
for d in dest:
    if not link or link[-1] < d:
        link.append(d)
    else:
        link[bisect_left(link, d)] = d
print(len(link))

def bisect_left(arr, val):
    s, e = 0, len(arr)-1
    while s <= e:
        m = (s+e)//2
        if arr[m] > val:
            e = m-1
        else:
            s = m+1
    return s

n = input()
dest = list(map(int, input().split()))
link = []
for d in dest:
    if not link or link[-1] < d:
        link.append(d)
    else:
        link[bisect_left(link, d)] = d
print(len(link))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다