[코딩테스트][백준] 🔥 백준 2568번 "전깃줄 - 2" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

import sys
from bisect import bisect_left

input=sys.stdin.readline

N=int(input())

arr=[]
allNum=set()

for _ in range(N):
    a,b=map(int,input().split())
    arr.append((a,b))
    allNum.add((a,b))

arr.sort()

tails=[]
tails_idx=[]
prev_idx=[-1]*N

for i in range(N):
    num=arr[i][1]
    pos=bisect_left(tails,num)
    if pos==len(tails):
        tails.append(num)
        tails_idx.append(i)
    else:
        tails[pos]=num
        tails_idx[pos]=i
    if pos>0:
        prev_idx[i]=tails_idx[pos-1]

print(N-len(tails))
k=tails_idx[-1] if tails_idx else -1
while k!=-1:
    allNum.remove(arr[k])
    k=prev_idx[k]

for t in sorted(allNum):
    print(t[0])

기존 전깃줄 문제의 알고리즘에서 이진탐색을 활용한 LIS로 바꾸면 되는 문제이다. 이진탐색을 활용한 LIS의 경우 이전 idx를 저장해서 최장 수열이 무엇인지 추적이 가능하므로 이를 활용하면 된다.

https://velog.io/@ouk/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89%EC%9C%BC%EB%A1%9C-%EB%B9%A0%EB%A5%B4%EA%B2%8C-%ED%91%B8%EB%8A%94-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8C%80%EA%B3%B5%EA%B0%9C

이렇게 Python로 백준의 "전깃줄 - 2" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊