문제
https://www.acmicpc.net/problem/10165
접근
- 문제를 봤을 때 우선 대강 정렬하고 스위핑해서 풀어야겠다고 생각했다.
- 까다로운 부분이 원형으로 이루어진 버스 노선 처리인데, 카카오 기출 문제 중 원을 두 배 늘려서 직선으로 처리했던게 떠올라서 직선으로 바꾸어 처리했다.
- 첫 번째 시도에서는 시간초과가 났는데 삭제할 노선을 저장할 때 배열 대신 딕셔너리를 사용했고, 이미 정렬된 상태이기 때문에 뒤에 나오는 버스 노선들은 현재 노선보다는 시작점이 무조건 같거나 크므로 끝점만 갱신하도록 변경했다.
- 이후 시도에서 부분 성공이 나와서 고민한 결과, 시작점이 같은데 끝점이 다른 두 노선에서 끝점이 큰 노선이 더 뒤로 정렬되는 경우가 반례라고 생각해서 시작점은 오름차순으로, 끝점은 내림차순으로 정렬되도록 정렬 조건을 주었다.
풀이
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
bus = []
for i in range(1, m + 1):
a, b = map(int, input().split())
if a < b:
bus.append((a, b, i))
bus.append((a + n, b + n, i))
else:
bus.append((a, b + n, i))
bus.sort(key=lambda x: (x[0], -x[1]))
deleted = dict()
rt = 0
for s, e, num in bus:
if e <= rt:
deleted[num] = True
else:
rt = e
for i in range(1, m + 1):
if i not in deleted:
print(i, end=" ")
'Python > Coding Test' 카테고리의 다른 글
16933 벽 부수고 이동하기 3 (0) | 2022.02.22 |
---|---|
9996 한국이 그리울 땐 서버에 접속하지 (0) | 2022.02.17 |
2749 피보나치 수 3 (0) | 2022.02.16 |
21939 문제 추천 시스템 Version 1 (0) | 2022.02.16 |
13334 철로 (0) | 2022.02.15 |