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

문제 요약

위와 같이 전봇대 A와 B 사이에 연결된 전깃줄을 모두 꼬이지 않게하면서 최소한으로 제거하는 방법을 찾는 문제이다.

이 문제의 난관은 제거해야하는 전깃줄을 오름차순으로 출력해야한다는 것이다.
위의 경우 [1, 2, 3] 총 3개를 제거한 것이며, [1, 3, 4] 3개를 제거하는 것도 답이 될 수 있다.

결론부터 말하자면 이 문제는 '가장 긴 증가하는 부분 수열(LIS)'의 심화문제라고 할 수 있다.

풀이

1. A와 B 중 하나를 정렬하기

제거된 전깃줄을 보면 (4, 1), (6, 4), (7, 6), (9, 7), (10, 10)으로 A를 기준으로 보나 B를 기준으로 보나 모두 오름차순 정렬되어있다는 것을 확인할 수 있다.

즉, A나 B 중 하나를 오름차순 정렬한 뒤에 이를 기준으로 나머지의 가장 긴 증가하는 부분 수열(LIS)을 구하면 가장 많은 전깃줄을 꼬이지 않게 연결할 수 있다.

A, B 순으로 각각 입력되므로 A를 기준으로 정렬하였다.

# A를 기준으로 정렬
arr = [tuple(map(int, input().split())) for _ in range(N)]
arr.sort(key = lambda x : x[0])

2. LIS의 길이 및 LIS의 마지막 인덱스 구하기

완전 탐색이라면 O(N^2)의 시간복잡도이지만, 이분 탐색을 통해 LIS의 길이와 LIS의 마지막 인덱스를 구할 수 있다.

이거는 직접 설명하면 풀이가 너무 길어질 것 같아 다른 분들이 잘 설명한 자료를 참고하면 좋을 것 같다.

[백준 12015 파이썬] 가장 긴 증가하는 부분 수열 2 (골드2, 이분 탐색)

위 내용을 이해하고 있다는 가정을 하에 나머지 과정을 작성하겠다.

이 문제에서 차이점이 있다면, 이분 탐색을 통해 길이를 구하는 과정에서 로깅을 해야한다는 것이다.

과정을 설명하면 다음과 같다.

1. 증가수열을 저장할 리스트(lis)와 로깅할 리스트(index_list)를 초기화한다.

• lis는 빈 배열을 선언
• index_list는 전깃줄 배열의 크기 N과 동일하고 1:1로 매핑된다.

2. index_list에는 전깃줄 정보가 lis 배열의 몇번 인덱스에 저장되었는지를 로깅한다.

동일과정을 반복하면 최종적으로 위와 같이 된다.

현재 구해진 lis는 실제 lis가 아니라, 실제 lis의 길이와 마지막 값이 무엇인지만 알 수 있는 상태이다.
위 예제에서 lis의 길이는 5이며, 마지막으로 (10, 10)을 갖는다는 것을 알 수 있다.

3. index_list를 기준으로 역탐색하며 실제 lis 구하기

이제 index_list를 역순으로 탐색하며 실제 LIS를 구한다.

• LIS의 길이가 5이므로 LIS의 마지막 인덱스는 4일 것이다. index_list[7] = 4이므로 7은 연결되어야 하는 전깃줄이다.
• 탐색 값을 1 줄여서 3을 찾는다. index_list[6] = 3이므로 6은 연결되어야 하는 전깃줄이다.
• 이 과정을 탐색값이 0이 될때까지 반복한다.
• 위 그림에서 알 수 있듯이 0, 1, 2 인덱스가 잘라내어야 할 전깃줄이며, 여기에 대응되는 [1, 2, 3]을 답으로 출력하면 된다.

코드

완벽히 최적화된 풀이가 아닙니다. 참고만 해주세요...

import sys

input = sys.stdin.readline

def binary_search(num, right):
    lo, hi = 0, right
    
    while lo < hi:
        mid = (lo + hi) // 2
        
        if sorted_arr[mid][1] < num:
            lo = mid + 1
        else:
            hi = mid

    return hi

if __name__=="__main__":
    N = int(input())
    arr = [tuple(map(int, input().split())) for _ in range(N)]
    arr.sort(key = lambda x : x[0])
    
    sorted_arr = [] # 교차하지 않는 전기줄
    index_list = [] # 로깅
    sorted_arr.append(arr[0])
    index_list.append(0)
    count = 1
    
    for i in range(1, N):
        if sorted_arr[-1][1] < arr[i][1]:
            sorted_arr.append(arr[i])
            index_list.append(count)
            count += 1
        else:
            idx = binary_search(arr[i][1], count)
            sorted_arr[idx] = arr[i]
            index_list.append(idx)
    # 최장 증가 수열 길이 출력
    print(N-count)
    
    # 저장한 로깅 리스트를 거꾸로 탐색하며 꼬이지 않은 전깃줄 구하기
    link_set = set() # 꼬이지 않은 전깃줄 번호 저장
    find_idx = count - 1
    for idx, inserted_idx in enumerate(index_list[::-1]):
        if inserted_idx == find_idx:
            link_set.add(N-idx-1)
            find_idx -= 1
        if find_idx < 0:
            break
    
    for i in range(N):
        if i not in link_set:
            print(arr[i][0])