[백준] 13334번 : 철로

13334번: 철로

13334번: 철로

🤔 문제분석

처음에는 이분탐색으로 문제를 접근하였습니다. 우선 시작, 종료 위치를 오름차순으로 정렬합니다. start = 가장 작은위치, end = 가장 끝에있는위치를 시작으로 이분탐색을 시작합니다. mid값을 구한다음, (mid, mid +d) 범위안에 있는 위치들을 카운팅 해줍니다. (mid, mid+d) 기준으로 왼쪽으로 있는 개수, 기준으로 오른쪽에 있는 개수를 카운팅한뒤 왼쪽이 더많다면 mid 값을 감소시키고 오른쪽이 더 많다면 mid값을 증가시켜가면서 최대 개수를 구합니다. 그러나 오른쪽에 치우치지않고 왼쪽에도 치우치지 않는 조건을 어떻게 처리해야할지 난관에 빠집니다 😢

 

그 다음으로 생각해본것이 우선순위큐를 활용한 문제 풀이입니다. 처음에는 끝나는 위치를 기준으로 생각해보았는데 발상의 전환으로 시작위치를 기준으로 접근하면 더 쉽게 문제를 해결 할 수 있습니다. 데이터의 정렬은 (끝나는위치, 시작위치) 순으로 오름차순 정렬합니다. 그리고 난뒤 배열을 순회하는데 끝나는위치 - d의 길이가 시작위치보다 작은 값들은 모두 우선순위 큐를 활용하여 pop 해버립니다. 이렇게 하면 순간순간 최대의 개수를 갖을 수 있는 조건이 됩니다.

💻 코드

이분탐색

import sys
input = sys.stdin.readline

n = int(input())

road = []
for _ in range(n):
    road.append((sorted(list(map(int, input().split())))))
    
road.sort(key=lambda x:x[0])

d = int(input())

start = road[0][0]
end = road[-1][1]
ans = 0
while end >= start:
    mid = (start+end)//2
    x1, x2 = mid, mid + d
    count, left, right = 0, 0, 0
    for s, e in road:
        if x1 <= s and e <= x2:
            count += 1
        elif s < x1 and e < x2:
            left += 1
        elif s > x1 and e > x2:
            right += 1
        else:
            if abs(x1 - s) >= abs(e - x2):
                left += 1
            else:
                right += 1
            
    ans = max(count, ans)
    if left >= right:
        end = mid - 1
    else:
        start = mid + 1

print(ans)

우선순위 큐

import sys
import heapq
input = sys.stdin.readline

n = int(input())

road = []
for _ in range(n):
    road.append((sorted(list(map(int, input().split())))))
    
road.sort(key=lambda x:(x[1], x[0]))

d = int(input())

ans = 0
queue = []
for s, e in road:
    heapq.heappush(queue ,s)
    
    line_start = e - d
    while queue and line_start > queue[0]:
        heapq.heappop(queue)
    
    ans = max(ans, len(queue))

print(ans)

🎯 피드백 및 개선사항

발상의 전환이 필요한 문제로, 다양한 조건에서 비교해보면서 자꾸 생각해봐야겠다는걸 깨닫았습니다. 정렬문제를 접하고 이제 어떤 방식으로 풀어야할지 감이 슬슬 잡혀가는데 아직 10% 부족한 감으로 문제를 해결하지 못하고 있습니다. 😎