[Python 3] BOJ - 2568 "전깃줄 2"

 # 문제 링크 : https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

 

 # 풀이 :

개인적으로 문제의 핵심은 가장 긴 증가하는 부분 수열, 즉 LIS를 유추할 수 있는지라고 생각한다. 왜냐하면 현재 왼쪽의 전봇대를 인덱스, 오른쪽의 전봇대를 값이라고 생각한다면, 문제의 조건에 따라 인덱스가 증가함에 따라 점점 고를 수 있는 값의 갯수는 줄지만 고른 값들은 모두 증가하는 방향으로 선택해야 한다.

i	0	1	2	3	4	5	6	7
A[i]	8	9	2	1	4	10	7	6
D[i]	8	?	?	?	?	?	?	?
Q[i]	1	?	?	?	?	?	?	?

<표 1. LIS 길이 예시>

 

 위의 표에서 배열 A는 LIS를 구해야 할 배열, 즉 원래 주어지는 배열이다. 배열 D는 결론적으로 말하면 '길이가 i + 1인 LIS 후보 중 i + 1번째 수 중 가장 작은 값'을 담는 배열이다. 따라서, 배열 D는 LIS 자체가 되는 것이 아니라, 단지 LIS의 길이만을 알 수 있다는 점이다. 따라서 'i번째 인덱스에서 만들 수 있는 LIS의 길이를 따로 저장'하는 배열 Q를 만들어 실제 LIS를 구할 수 있게 만들어야 한다.

 우선 LIS의 정의부터 살펴보면, 거창할 것 없이 '가장 큰 증가하는 부분 수열'이다. 따라서 인덱스가 증가함에 따라 증가하는 수를 고르면 된다. 단, 연속일 필요는 없다. 따라서 반드시 배열이 증가하는 부분으로 변해야 한다. 따라서 지금 가리키는 A[i]의 값이 만일 D[i]보다 크다면, D는 그래도 증가하는 순서를 유지하므로, 정의가 깨지지 않는다. 따라서, D[1]의 '?'에 들어갈 값은 9다. 또한 이제 LIS의 길이가 2로 늘어 났으므로 Q[1] = 2라고 할 수 있다.

 그러나, 현재 i가 2라면, 배열 D의 마지막 값인 9보다 작다. 따라서 더이상 LIS가 진행될 수 없다. 그렇다면 2는 넣지 말아야 하는가? 그것은 아니다. 왜냐하면 2를 시작으로 하는 LIS를 다시 만드는 경우의 수가 있기 때문이다. 그렇다면, 2는 8보다도 작으므로 [2, 8, 9]가 되어야 할까? 그것도 아니다. 왜냐하면 배열 D의 정의가 길이에 위배되기 때문이다. D[0]은 길이가 1인 LIS 중 가장 작은 값이 되어야 하기 때문에, [2], [8], [9] 모두 하나씩 놓고 보면 3가지 경우 모두 길이가 1인 LIS인 후보들이다. 따라서 D[0]은 8이 아니라 2가 되어야 한다. 한편, D[1]은 길이가 2인 LIS인 경우이므로 이 경우는 [8, 9] 하나 밖에 없다. 그 중 2번째 수인 9가 여전히 길이 2인 LIS 후보 중 가장 작은 두번째 수이므로 9는 그대로 유지된다.

 이때, A[2]인 2는 길이가 1인 LIS이므로 앞서 길이가 2였던 [8,9]인 LIS를 이어나갈 수 없으므로 Q[2] = 1이다.

i	0	1	2	3	4	5	6	7
A[i]	8	9	2	1	4	10	7	6
D[i]	1	9	?	?	?	?	?	?
Q[i]	1	2	1	1

<표 2. LIS 길이 예시 >

 

 위의 과정을 인덱스 3까지 진행했다고 가정했을때, 예상되는 배열 D, Q는 위 표 2와 같다. Q는 무조건 인덱스가 for문을 돌아감에 따라 채워지게 되는데, 항상 그 인덱스에서는 앞의 LIS의 길이가 이어지느냐, 그렇지 않느냐의 경우에 속할 수 밖에 없기 때문이다. 반대로, 배열 D는 현재 모든 경우에서 D[2], 즉 길이가 3짜리인 LIS를 만들 수 있는 경우가 없기 때문이다.

 이제 현재 인덱스가 4를 가리키는 경우를 생각하면, 위 표1의 과정과는 다른 경우를 생각해보아야 한다. 현재 A[4]인 4는 [4] 혹은 [1, 4]로 두 가지 경우가 있다. 즉, LIS의 길이가 2가 되는 후보가 하나 추가된 것이다. 따라서 [8, 9]와 [1, 4]의 두 후보중 두번째 숫자는 각각 9와 4인데, 배열 D의 정의에 따라 더 작은 수가 들어 가야 하므로 D[2]는 4로 변경된다.

i	0	1	2	3	4	5	6	7
A[i]	8	9	2	1	4	10	7	6
D[i]	1	4	6
Q[i]	1	2	1	1	1	3	2	2

<표 3. 최종 결과>

 

모든 과정을 거치고 나면, 순차적으로 LIS의 길이를 이루지 않는 부분을 체크하면 문제의 정답이 된다.

 

 # 코드 

import sys
# lower_bound : 배열 a의 원소 중, x보다 작거나 같은 값 중 가장 큰 값의 위치 리턴
#               가능한 LIS의 길이를 빠르게 찾기 위함 
def lower_bound(left, right, a, x):
    while left <= right:
        mid = (left + right) // 2
        if a[mid] >= x:
            right = mid - 1
        else:
            left = mid + 1
    return left

n = int(sys.stdin.readline())
a = []
for i in range(n):
    start, end = map(int, sys.stdin.readline().split())
    a.append((start, end))
    
# 인덱스 순으로 정렬
a.sort(key=lambda x : x[0])
d = [a[0][1]]
q = [-1] * n
for i in range(n):
	# 현재 값이 D의 마지막 값보다 큰 경우 - LIS 길이 증가하므로 Q는 1증가, D에는 A[i]를 추가
    if d[-1] < a[i][1]:
        q[i] = max(q) + 1
        d.append(a[i][1])
    else:
    	# x = 현재 수 A[i]가 만들 수 있는 최대 길이 - 1 
        x = lower_bound(0,len(d) - 1, d, a[i][1])
        if a[i][1] > d[x]:
            d[-1] = a[i][1]
        else:
            d[x] = a[i][1]
            q[i] = x + 1

print(n - len(d))
r = len(d)
w = []

# 배열 Q를 뒤부터 순회하여 실제 LIS를 저장한다
for i in range(n - 1, -1, -1):
    if r == 0:
        break
    if q[i] == r:
        w.append(a[i])
        r -= 1
        
# 실제 LIS가 아닌 원소들을 저장
c = []
for i in a:
    if i not in w:
      c.append(i)
      
# 인덱스 순으로 배열 C를 정렬
c.sort(key=lambda x : x[0])
for i in range(n - len(d)):
    print(c[i][0])