[BOJ] 백준 13334 철로 (JAVA)
Algorithm/- Baekjoon2024. 5. 9. 02:35[BOJ] 백준 13334 철로 (JAVA)

📑 문제🌱 아이디어스위핑 유형의 문제, 일단 무엇을 기준으로 정렬할지 생각해 보자 위 문제에 핵심은 좌표의 범위 L이 주어질 때  end - start 이 만족해야 한다, 즉 구간마다 L범위에 해당하는선분의 개수를 세야 한다. 좌표 구간마다 선분이 해당하는지 판단하고, 범위체크까지 한다면 자칫 O(N^2) 시간복잡도를 가지게 구현할 수 있다.하지만 N의 범위가 100,000까지 이며 O(N) 이하로 구현해야 한다. 먼저 데이터를 정렬하는 과정이 필요하다. y축을 기준으로 정렬하고 한쪽 방향으로 쭉 스캔하면서 계산을 하면 된다즉 한쪽 -> 반대쪽으로 쭉 스캔을 하는 스위핑 방식으로 구현하면 O(N)의 시간복잡도로 빠르게 구현 가능하다.   정렬 후 가장 아래 (10, 20)부터 last에 x를 넣고 계..

반응형
image