[BOJ] 2568 - 전깃줄 - 2 (Python)

 

 

아이디어

 

A전봇대 위치 번호를 기준으로 전깃줄을 내림차순 정렬 후 B전봇대 위치 번호의 최장 감소 수열을 구한다.

이후 최장 감소 수열에 포함되지 않은 전깃줄의 A전봇대 위치 번호를 출력한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    lines = sorted([tuple(map(int, input().split())) for _ in range(N)], reverse=True)
    LDS = [lines[0][1]]
    idx_list = [0]*N
    cnt = 1
    for i in range(1, N):
        if lines[i][1] < LDS[-1]:
            LDS.append(lines[i][1])
            idx_list[i] = cnt
            cnt += 1
        else:
            s = 0
            e = cnt-1
            while s <= e:
                m = (s+e)//2
                if LDS[m] > lines[i][1]:
                    s = m+1
                elif LDS[m] < lines[i][1]:
                    e = m-1
                else:
                    LDS[m] = lines[i][1]
                    idx_list[i] = m
                    break
            else:
                LDS[s] = lines[i][1]
                idx_list[i] = s
    res = []
    idx = cnt-1
    for i in range(N-1, -1, -1):
        if idx_list[i] == idx:
            idx -= 1
        else:
            res.append(f'{lines[i][0]}')
    print(N-cnt)
    print('\n'.join(res))

solution()