백준[10165] 버스 노선 (Python3)

관찰이 필요한 정렬 문제

막상 풀고 보면 그렇게 어렵진 않은데, 순환 구조 때문에 생각이 계속 꼬였다.

 

지문 분석

맨 처음엔 0번 정류소를 지나치는 노선을 2개로 분리해서 볼려 했지만 시간 초과를 받았다.
또한, 분리된 두 노선이 다른 어떤 노선과 포함되거나 포함하는지를 검증하는 과정이 매우 까다로웠다.

따라서, 노선을 쪼개기보다는 각 노선 시작점 또는 도착점 위치를 변경하는 방식으로 풀이를 생각했다.

시도한 방법 1

정류장이 원형이 아닌 무한한 일자 형태라고 가정한다.
0번 정류소를 지나치는 노선 중, 시작점과 0번 정류소 간의 거리가 가장 긴 값을 찾는다.
그 후, 모든 정류소 시작, 도착 위치를 그 값만큼 더해준다.
이 경우 예제 2번이 반례가 됐다.

시도한 방법 2

각 노선들의 시작점과 도착점을 적절히 조절하면 해결할 수 있단 확신이 들었다.
조절의 기준은 시작점 > 도착점인 경우이며, 조절해 주는 값은 N이다.

 

현재 문제가 되는 것이 0을 지나게 되면 정류소 숫자가 오름차순으로 가다 꺾인다는 것이다.
따라서, 시작점 > 도착점인 경우, 도착점에다 + N을 해, 시작점 < 도착점으로 만들어 줬다.

 

반대의 경우에는
원본 값과 각 지점 값을 + N 한 쌍을 추가로 넣었다.
즉, (시작점 + N, 도착점 + N)을 넣었다.

 

이걸 해준 이유는 예제 2의 4번 노선의 경우 [9, 26]로 표현되는데
만약 [4, 5]인 노선이 있다면, 이 4번 노선에 포함이 되지 않는다.

따라서 각 지점 값을 + N 해준다면, [4, 5] -> [24, 25]가 되기 때문에 4번 노선과 비교가 쉬워진다.

원본 값을 넣는 이유는 마찬가지로 [18,19]인 노선이 있을 때, 각 지점 값을 + N 해준다면,
[18, 19] -> [28, 29]가 돼서 4번 노선에 포함되지 않는 걸로 계산이 되기 때문이다.

 

정리하면 다음과 같다.

• 시작점 < 도착점
  시작점, 도착점
  시작점 + N, 도착점 + N
• 시작점 >= 도착점
  시작점, 도착점 + N

from collections import deque

def main():
    N = int(input())
    M = int(input())
    lines = deque()
    visit = [False] * (M + 1)
    for i in range(1, M + 1):
        s, e = map(int, input().split())
        if s < e:
            lines.append((s, e, i))
            lines.append((s + N, e + N, i))
        else:
            lines.append((s, e + N, i))

    lines = sorted(lines, key=lambda x: (x[0], -x[1]))

    for i in range(0, len(lines)):
        i_start, i_end, i_index = lines[i][0], lines[i][1], lines[i][2]
        if visit[i_index]:
            continue
        for j in range(i + 1, len(lines)):
            j_start, j_end, j_index = lines[j][0], lines[j][1], lines[j][2]
            if visit[j_index]:
                continue
            if i_start <= j_start and j_end <= i_end:
                visit[j_index] = True
            else:
                break

    for i in range(1, M + 1):
        if not visit[i]:
            print(i, end = " ")


if __name__ == "__main__":
	main()