🏫 전깃줄 - 2 (Class 5++)

👉🏻 2568번: 전깃줄 - 2

import sys; input=sys.stdin.readline
from bisect import bisect_left

N = int(input())
loc = sorted([list(map(int, input().split())) for _ in range(N)])

# LIS를 위해 B 값들 저장
dp = []

# 각 전깃줄이 LIS의 어느 인덱스에 들어갔는지 저장
pos = [0] * N

# 실제 LIS 구하는 과정과 인덱스까지 저장하는 로직 !
for i in range(N):
    b = loc[i][1]
    idx = bisect_left(dp, b)
    
    if idx == len(dp):
        dp.append(b)
    else:
        dp[idx] = b
    
    pos[i] = idx

len_dp = len(dp)
print(N - len_dp)

# 이번에는 LIS에 포함된 인덱스 역추적하기
need = len_dp - 1
keep = set()

for i in range(N-1, -1, -1):
    if pos[i] == need:
        keep.add(i)
        need -= 1
        
        if need < 0:
            break

# 제거해야 할 A 값들
for i in range(N):
    if i not in keep:
        print(loc[i][0])

 

---

왜 이렇게 풀었을까?

• 해당 문제는 LIS(최장 증가 부분 수열) 문제로 유명한 전깃줄 문제입니다.
• 이 문제를 가장 간단하게 푸는 방법은 DP로 접근하는 것인데, DP로 접근하게 되면 최악의 경우, 시간 복잡도가 O(N^2)까지 나오기 때문에, 최적으로 LIS 배열을 늘릴 수 있는 이분 탐색을 선택했습니다.
• LIS는 일단 dp[-1]보다 들어오는 값이 더 크면, dp에 들어오는 값을 추가하고, 아니면 이분 탐색으로 들어가야할 위치를 찾아 대체하는 방식으로 풀이하곤 합니다.
  • 이 문제는 LIS의 길이뿐만 아니라 제거되는 전깃줄의 인덱스도 함께 요구하고 있기 때문에, LIS의 따른 인덱스까지 함께 저장해 이 인덱스 배열을 역추적함으로써 오름차순으로 출력할 수 있게 구현하였습니다.
• 기존의 전깃줄 문제에 더해 인덱스를 다시 빼오는 요구사항이 이 문제를 플레로 만들지 않았나... 싶습니다.
• 그리고 심화 문제로 갈수록 이분 탐색과 bisect 모듈의 소중함을 동시에 느끼고 있는 것 같습니다.