[ 백준 ][ 골드5 ] 2565번 - 전깃줄 ( PYTHON 파이썬 )

링크 : https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

코드

---

import bisect

def LIS(arr):
    res = [arr[0]]
    for x in arr[1:]:
        if x < res[-1]:
            res[bisect.bisect_left(res,x)] = x
            continue
        res.append(x)
    return len(res)
    
n = int(input())
line = sorted([list(map(int,input().split())) for _ in range(n)])
print(n-LIS([x[1] for x in line]))

 

풀이

---

LIS(가장 긴 증가하는 부분수열) 알고리즘으로 해결했다.

LIS는 단순 DP로 해결할 수 있는 문제이지만 공간복잡도와 시간복잡도를 줄이려면 이분탐색을 이용해야 한다.

 

이분탐색을 이용한 LIS알고리즘은 다음과 같다.

• res배열을 하나 만들고 그 안에 숫자를 append하거나 바꾼다.
• res배열의 초기원소는 탐색하는 배열의 첫번째 원소이다.
• 탐색하고자 하는 배열의 두번쨰 원소부터 탐색하며 배열의 가장 마지막 원소와 크기를 비교한다.
• 중복이 허용되지 않는다는 조건이 있기 때문에 마지막 원소보다 작은지 큰지만 확인한다.
• 마지막 원소보다 크다면 배열에 append해준다.
• 마지막 원소보다 작다면 이분탐색을 통해 원소가 들어갈 인덱스를 구해준다. 
• bisect로 나온 인덱스의 값과 원소의 값을 바꿔준다.

 

여기서 bisect_left와 bisect_right에 대해 차이점에 대해 공부했다.

• bisect_left : 정렬된 배열에 원소를 삽입할 위치를 알려주는데 원소가 이미 배열에 있다면 기존 항목의 앞의 위치를 알려준다.
• bisect_right: left와 비슷하나 기존 항목 뒤의 위치를 반환한다.

여기서 우리는 bisect_left를 사용했는데 사실 중복이 허용되지 않는 배열에서는 left나 right나 상관없이 똑같은 결과가 나온다.