[백준]_2568번 : 전깃줄 - 2(파이썬)

2568번: 전깃줄 - 2

일단 아이디어 자체는 전깃줄과 다를 바가 없다. 꼬인 전깃줄을 꼬이지 않게 하기 위해서는 전깃줄을 하나의 쌍(예를 들어 [1, 8])으로 묶은 다음에 첫 번째 요소에 대해 정렬을 진행한 다음에 두 번째 요소의 LIS(최장 부분 수열)를 구하면 된다. 애초에 전깃줄의 꼬임이 왜 발생하는지에 대해 생각해 보면 이해하기 수월해진다. 전깃줄은 다음과 같은 조건을 만족시킬 때 꼬인다.

• 왼쪽 전봇대의 전깃줄을 a1, b1 이라고 하고 그에 대응하는(이어져 있는) 오른쪽 전봇대에 있는 전깃줄의 위치를 a2, b2라고 하자. 이때 a1 < b1 와 a2 > b2를 동시에 만족하면 전깃줄은 꼬여있다.  

이제 LIS문제인 것도 파악하였으니 본격적으로 알고리즘을 적용해 보자.

O(NlogN) 동적 계획법 

이 문제에서는 동적 계획법을 처음 배웠을 때 알게 된 방법과 약간 다른 접근을 해야 한다. 왜냐하면 전깃줄의 개수가 10만 개까지 늘어날 수 있기 때문에 기존의 O(N^2) 방법을 사용하면 시간초과가 나기 때문이다. 

 

시도 1(Python)

import sys
input=sys.stdin.readline
# ls는 전깃줄의 쌍을 튜플로 저장하는 리스트
# track는 최장 길이를 구하는 데에 사용되는 리스트
# arr는 제거해야 하는 전깃줄을 구하는 데에 사용되는 리스트
ls, track, arr = [], [], []
n=int(input())
for _ in range(n):
    a, b = map(int, input().split())
    ls.append((a, b)) # 튜플로 저장
    
ls.sort() # 첫 번째 전봇대에 대해서 정렬, 즉 최장 부분 수열은 정렬에 의해 생성된 두 번째 전봇대로 찾아야 함.

for _, s in ls: # 전깃줄의 두 번째 요소만 필요하므로 s로 둠.
    left, right = 0, len(track)-1
    while left<=right:
        mid = (left+right)//2
        if track[mid]<s:left=mid+1
        else:right=mid-1
    if left!=len(track):track[left]=s
    else:track.append(s)
    arr.append(left+1)
    # left는 사실 ls에서 처음 원소부터 s까지 최장 부분 수열의 길이를 알려주는 척도임
    
ans=len(track) # track에 저장된 값들은 제거하지 말아야할 전깃줄의 번호와 관련이 없다!!
print(n-ans) # 최장 길이 정답 출력
use=[] # 제거해야 할 전깃줄 답 출력용 리스트

for i in range(len(arr)-1, -1, -1): # 최장 길이에 해당하는 원소들을 arr에서 찾음
    if arr[i]==ans: ans-=1
    else: use.append(ls[i][0])
    
for num in use[::-1]: # 역순으로 출력
    print(num)

 

아마도 가장 이해가 안 가는 부분은 use=[ ] 다음의 부분일 것이다. 입력 예제인

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

를 이용해 보자. 아래의 코드를 use=[ ]에 붙이면 다음과 같은 결과를 얻을 수 있다.

for i in range(n):
    print(ls[i][1], end=' ')
print( )
print(arr)

결과 -> 

ls [?][1] : 8 2 9 1 4 6 7 10 
arr : [1, 1, 2, 1, 2, 3, 4, 5]

 

현재 ans에는 5가 저장되어 있다, 즉 최장 부분 수열의 길이가 5라는 뜻이다. 최장 부분 수열에 포함되는 숫자가 무엇인지만 알면 그것의 여집합을 찾아서 제거해야 할 전깃줄이 어디에 있는지 알 수 있는 것이다. 그래서 우리는 진작에 arr에 그 정보들을 저장해 온 것이다.

 

따라서 8까지의 lis는 1, 2까지는 1, 9까지는 2, 1까지는 1, 4까지는 2.... 이런 형태로 값이 저장된 것이다. 

 

즉 arr의 맨 뒷부분부터 시작해서 ans가 ans-1, ans-2, ans-3..., 1이 되는 부분을 arr에서 찾아나가면 최장 부분 수열에 누가 원소로 있는지 알 수 있는 것이다. 역으로 ans-i 순서에 해당하지 않은 전깃줄을 use로 보내버리면 되는 것이다. 

 

우리의 예제 입력으로 예를 들자면 ans의 갑이 5기 때문에 arr의 맨 뒤에서 5부터 탐색을 시작한다.

5를 바로 찾았으므로 ans를 1 감소시킨 4로 정정한다.

4를 바로 찾았으므로 ans를 1 감소 시킨 3으로 정정한다.

3을 바로 찾았으므로 ans를 1 감소시킨 2로 정정한다.

2를 바로 찾았으므로 ans를 1 감소 시킨 1로 정정한다.

1을 바로 찾았으므로 ans를 1 감소시킨 0으로 정정한다.

이후에 나오는 2, 1, 1은 0과 일치하지 않으므로 그에 해당하는 9, 2, 8의 첫 번째 전깃줄인 3, 2, 1을 use 리스트에 담는다.

 

use에는 전깃줄이 역순으로 들어갔기 때문에 역순(use [::-1])으로 출력한다.