[백준] 2568번: 전깃줄2 - python3

문제 출처:https://www.acmicpc.net/problem/2568

---

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 최소 개수의 전깃줄을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. 

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 A전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.

바로 전 게시글에서 이어지는 문제입니다.

이번에도 없애야 하는 전깃줄의 최소 개수를 출력하는데 플러스로 없애야 하는 전봇대의 위치까지 알아내야 합니다.

일단 전 게시글에서 알려준 방법으로 없애야 하는 전봇대의 최소 길이부터 구해봅시다.

LIS의 길이를 구하는 방법을 모른다면 (1365번: 꼬인 전깃줄) 를 보고 오시면 됩니다.

예시는 위 그림에 있는 수열[ 4, 2, 6, 7, 9, 1, 3, 10 ]을 그대로 쓰겠습니다. 

위 수열에 LIS알고리즘을 사용한다면 [ 3, 6, 7, 9, 10 ] 의 결과가 나옵니다 이 수열의 길이가 LIS의 길이가 됩니다. 

단 이 수열이 LIS을 구성하는 수열은 아닙니다 딱 보더라도 제일 앞에 있는 3은 원본 수열에서 뒤쪽에 있는 수입니다. 

따라서 LIS의 요소까지 구하려면 추가적인 연산을 해주어야 하는데 이제부터 그 방법을 설명 하겠습니다.

일단 기존에 하던대로 LIS알고리즘을 수행합니다 단 수행하면서 입력되는 수가 LIS배열의 몇 번째 칸에 들어가는지 기록 

할 배열이 하나 더 필요합니다. 그림으로 표현하면 아래와 같습니다.

이 구해진 Record배열의 제일 뒤부터 순차적인 내림차순 즉 Record 배열의 제일 마지막이 5 이므로 5, 4, 3, 2, 1순으로 

원본 배열의 인덱스에 맞춰 데이터를 추가해주면 LIS 의 요소를 구할 수 있습니다. 

최종적인 수열 [ 2, 6, 7, 9, 10 ] 이 LIS 요소까지 구성하는 수열이 됩니다.

문제의 정답은 LIS를 만들기 위해 없애야 하는 전봇대를 구하는 것 입니다. 

따라서 원본 수열에서 최종적으로 구해진 LIS의 요소들을 전부 빼고 남은 숫자들이 없애야 하는 전봇대가 됩니다.

전체 코드입니다.

def Lower_Bound(lst, num):
    low = 0
    high = len(lst) - 1
    while (low < high):
        mid = int((low + high) / 2)
        if num <= lst[mid]:
            high = mid
        elif num > lst[mid]:
            low = mid + 1
    return high
 
 
dic = {}
lst = []
lis = [-1]
result = []
backtrace = []
n = int(input())
for i in range(n):
    a, b = map(int, input().split(' '))
    dic[b] = a
temp = sorted(dic)
for i in temp:
    lst.append(dic.get(i))
for i in lst:
    if i > lis[-1]:
        lis.append(i)
    else:
        lis[Lower_Bound(lis, i)] = i
    result.append(lis.index(i)+1)
lisLength = len(lis)
for i in range(len(lst)-1,-1,-1):
    if result[i] == lisLength:
        backtrace.append(lst[i])
        lisLength-=1
print(n - (len(lis) - 1))
lst.sort()
for i in backtrace:
    lst.remove(i)
for i in lst:
    print(i)