[백준 13334번] 철로 (Python3)

import sys
input = sys.stdin.readline

N = int(input())

info = []
for i in range(N):
  info.append(tuple(sorted(map(int,input().split()))))
D = int(input())

home = []
com = []
for i in range(N):
  h,c = info[i]
  if c-h > D:
    continue
  home.append(h)
  com.append(c)

home.sort()
com.sort()
N = len(home)

cnt = result = 0
start = end = 0
while True:
  if start == N:
    break
  if start != 0:
    cnt -= 1
    if h == home[start]:
      start += 1
      continue
  h = home[start]
  while end<N and com[end] <= h+D:
    end += 1
    cnt += 1
    result = max(cnt,result)
  start += 1

print(result)

 

투 포인터 알고리즘을 이용해서 해결하였다.

 

요약하면

1. 집 좌표와 회사 좌표 중 더 작은 좌표를 집 좌표라고 가정한다.

2. 집 좌표와 회사 좌표간의 거리가 D를 넘는 경우는 필요 없으므로 제외한다.

3. 집 좌표 따로, 회사 좌표 따로 sort한다.

4. 가장 작은 집 좌표에서 시작, (집좌표 + D) 거리까지 존재하는 회사 개수만큼 + 해준다.

5. 다음 집 좌표로 이동할때마다 집이 하나씩 범위 밖으로 나가므로 -1을 해준다.

 

처음에는 투포인트 + 투포인트 로 4포인트 알고리즘처럼 풀려고 했었다.

그러다가 집과 회사사이의 거리가 D를 넘는 경우를 제외하면 투포인트로 풀 수 있다는 것을 알게되었다.

 

다른 사람들은 heapq를 이용해서 푼 경우가 많았다. 사실 원리 자체는 거의 똑같다. sort를 쓰느냐 heapq를 쓰느냐의 차이라서

 

 

오늘의 교훈) 불필요한 조건을 제외하고 문제를 해결하자