[BOJ]1931.py

진짜 오랜만에 알고리즘 푸는데..
플레 가야지(?)

1931 풀이

해답

def solution(N, M:list):

    if len(M) == 1:
        return 1

    M.sort(key=lambda x : (x[0], x[1]))
    stack = [M[0]]

    for m in M[1:]:

        before = stack.pop()
        now = m

        if before[1] <= now[0]:
            stack.append(before)
            stack.append(now)
            continue
        
        if before[1] > now[1]:
            stack.append(now)
            continue
        
        stack.append(before)

    return len(stack)


N = int(input())
M = []

for _ in range(N):
    M.append(list(map(int, input().split())))


print(solution(N, M))
    

• 어차피 정렬을 해서 비교하므로 바로 직전의 것만 비교하도록 함

2
1 2
1 1
2

• 위의 경우에 대비해서 정렬 시 M.sort(key=lambda x : (x[0], x[1])) 두번째 값도 정렬을 해줘야 한다