[Python] 10165번: 버스 노선(플레 처음으로 성공한 날)

https://www.acmicpc.net/problem/10165

10165번: 버스 노선

import sys
input = sys.stdin.readline


def getIsRemainer(info):
    info.sort(reverse=True, key=lambda x: x[1])
    info.sort(key=lambda x: x[0])
    
    isRemainer = [True for _ in range(M)]
    maxB = 0
    for _, b, c in info:
        if maxB < b:
            maxB = b
        else:
            isRemainer[c-1] = False

    return isRemainer


def printIsRemainer(isRemainer):
    curRoute = 1
    for b in isRemainer:
        if b:
            print(curRoute, end=" ")
        curRoute += 1


if __name__ == '__main__':
    N = int(input())
    M = int(input())

    info = []
    for i in range(M):
        a, b = map(int, input().split())
        if a < b:
            info += [(a, b, i+1), (a+N, b+N, i+1)]
        else:
            info.append((a, b+N, i+1))

    isRemainer = getIsRemainer(info)
    printIsRemainer(isRemainer)

이 문제를 풀기 위한 포인트가 딱 2가지가 있다.

 

처음은, info라는 곳에 입력받은 노선의 정보를 저장할 것인데, 원형의 형태를 하고 있으므로 조금 특이한 방식으로 정보를 저장한다. 이 때 두 경우로 나누어 정보를 저장한다.

첫번째 경우로 a < b일 때에는, 정말 일반적인 경우이므로 a, b를 그대로 저장할 것 같지만 a, b와 더불어 a+N, b+N의 정보까지 저장하는데 이렇게 하는 이유는 두번째 경우를 저장하는 방식 때문이다.

두번째 경우는 '5 0'과 같이 뒤의 숫자가 더 큰 경우(이 때 a > b가 아니라, else로 조건을 단 이유는, 문제 조건 상 a==b라는 입력은 없다고 하였기 때문이다.)인데, 이 때 a, b+N의 형태로 저장한다. 즉, 예시 케이스 1번의 경우에는 '5 0'이 5, 10으로 저장된다는 것이다.

이런 식으로 저장하게 되면 정보의 양은 늘어나지만 범위 체크를 정확히 할 수 있게 된다. 가령, 예시 입력 1에서의 '5 0', '7 9'의 경우 (5, 10, 2), (7, 9, 3)이 저장되어 '7 9'가 '5 0'에 속한다는 사실을 쉽게 알 수 있다는 것이다.

 

이후에는 getIsRemainer() 함수를 통해 어떤 노선들이 남는지를 기록하는 isRemainer를 얻어와야한다. 해당 함수는 info를 2번 정렬하는 것으로 시작한다. 이에 대해선 이후 내용에 대해 설명하면서 후설하겠다. 일단은 노선의 시작 지점을 기준으로 오름차순 정렬했다는 것만 인지하자.

아무튼 가장 핵심적인 for문에 대해서 설명하겠다. 우선 정렬된 info의 값은 아래와 같다.

(0, 4, 1), (2, 6, 2), (5, 10, 3), (7, 9, 4), (9, 14, 5), (10, 14, 1), (12, 16, 2), (17, 19, 4)

시작지점을 기준으로 오름차순 정렬인 것을 유의하며 생각해보자. 0 4 1이 2 6 2 이전에 있다. 2 6이 0 4에 포함되지 않는 이유는 바로 끝나는 지점이 2 6이 더 크기 때문이다. 따라서 (이전에 나왔던 b의 최댓값)이 (현재 for문을 통해 돌고 있는 b) 이상일 경우, 현재의 노선이 그 최댓값에 해당하는 노선에 속해있다고 볼 수 있다. 이에 따라, 만약 현재의 b가 maxB보다 크면 maxB를 갱신시켜주고, 나머지 경우에는 isRemainer를 False로 만들어주면 된다.

 

이렇게 isRemainer를 전달하여 printIsRemainer()를 통해 출력해주면 끝이다.

 

 

여담으로 오늘 플레티넘 수준의 문제를 처음 풀어봤는데, 코드가 생각보다 복잡하지 않았고 그저 '똑똑한 풀이'만 고안해낼 줄 알면 풀 수 있는 것 같다.