[Python] 백준 철로(13334) 문제 해결 과정 (투포인터에서 우선순위 큐)

 

1. 백준 13334번(곱셈)

 

https://www.acmicpc.net/problem/13334

안녕하세요! FlyDuck_Dev🦢 입니다.

오늘은 백준 13334번 철로 문제를 푸는 해결 과정을 정리하는 포스팅을 작성해보도록 하겠습니다. 

 

 

2. 기존 풀이

 

left, right 투포인터를 잡고 각각 선분 d의 시작과 끝이라고 생각하고,

left를 통근자들의 home 좌표 기준을 삼아 D만큼(백준 문제에서의 L) 밀면서 사실상의 완전탐색 형식으로 문제를 풀면 되겠다고 생각해서 아래와 같이 코드를 작성하였습니다.

a = int(input())
dis = []
for i in range(a):
    dis.append(tuple(map(int, input().split())))

d = int(input())

dis.sort() # 자료구조 [(5, 40), (10, 20), (10, 25), (30, 25), (30, 50), (35, 25), (50, 60), (80, 100)]

idx = 0
left = 0
right = 0
temp_cnt = 0
max_cnt = 0

while idx < a:

    left = dis[idx][0]
    right = left + d
    
    for h,o in dis:
        if h > o:
            h, o = o, h
        if h >= left and o <= right:
            #print(h,o,left,right)
            temp_cnt +=1

    if max_cnt < temp_cnt:
        max_cnt = temp_cnt

    idx += 1
    temp_cnt = 0


print(max_cnt)

백준에 나와있는 예제입출력은 다 통과하였고 사고 과정은 아래와 같습니다.

 

길이가 d인 모든 선분 중에서 집과 사무실의 위치가 모두 포함되는 사람들의 최대 수를 구하기 위해서 left, right를 길이가 d인 선분의 끝점으로 잡고 이동시키면서 그 범위 안에 포함되는 집과 사무실 위치를 가진 사람들의 수를 구하고, 이 중에서 최대값을 구하고자 하였습니다.

구체적인 알고리즘 과정은 다음과 같이 작성하였습니다.

1. 사람들의 집과 사무실 위치를 입력 받아 (h, o) * a의 리스트를 만든다.
2. dis 리스트를 튜플 0번째 인덱스를 기준으로 정렬한다.
3. 길이가 d인 선분을 이동시키면서 그 선분에 포함되는 집과 사무실 위치를 가진 사람들의 수를 구한다.

• 선분의 왼쪽 끝 위치를 left, 오른쪽 끝 위치를 right로 설정한다. (처음에는 left를 첫 번째 사람의 집 위치로 설정한다.)
• 오름차순으로 정렬한 리스트에서 순차적으로 집과 사무실 위치를 검사하다.
• 모든 사람에 대해서 검사를 마치면, temp_cnt와 max_cnt를 비교하여 max_cnt를 갱신한다.
• 다음 선분을 검사하기 위해 left를 다음 사람의 집 위치로 설정하고 반복한다.

그러나 N^2 방식이  O(10만 * 10만)의 시간복잡도가 되어 1초를 넘기게 되어, 전략 변경 불가피

 

 

3. 우선순위 큐로 변경

 

접근 방식 변경:
정렬 후 투포인터 -> 정렬 후 우선순위 큐(최소 힙)

 

 

사람 수 만큼 순회하면서 차근차근 우선순위 큐에 home(좌표)를 heappush 하고

 

통근 선분들의 오른쪽 끝 점(office 좌표값)을, 철로의 오른쪽 끝 점이라고 가정하여 'office좌표에서 D값을 뺀 만큼의 값'이 home 좌표보다 더 크면 철로 안에 home이 없다고 판정할 수 있고, while문을 이용해서 철로 안에 home이 들어오지 않은 경우들을 모조리 우선순위 큐에서 다 뽑아내주었습니다.

 

더 이상 우선순위 큐 안에 선분 안에 들어오지 않는 home이 없다고 판단한다면, 지금까지 우선순위 큐에 쌓인 home 원소의 통근자들은 전부 집과 사무실의 위치가 모두 D에 포함되므로 그 시점의 우선순위 큐의 길이와 기존 최대치 우선순위 큐의 길이를 담아두는 answer을 비교하여 더 큰 값을 게속 answer에 담을 수 있도록 전략을 변경하였습니다.

import heapq ,sys

a = int(sys.stdin.readline().strip())
dis = []
for i in range(a):
    h, o = map(int, sys.stdin.readline().strip().split())
    dis.append((min(h,o), max(h,o)))
dis.sort()
d = int(input())

heap_arr = []
answer = 0

for i in range(a):
    if abs(dis[i][1]-dis[i][0]) <= d:
        heapq.heappush(heap_arr,dis[i][0])
        while heap_arr and heap_arr[0] < dis[i][1] - d:
             heapq.heappop(heap_arr)
        answer = max(answer, len(heap_arr))
print(answer)

 

그렇지만 에러가 났습니다. 백준 게시판을 샅샅이 살펴보니 아래와 같은 반례 케이스가 있었습니다.

4
1 4
1 4
2 5
3 4
3

ANSWER: 3

OUTPUT: 2

해당 반례에서는 1부터 3까지의 선분 안에

( 1 4 ) ( 1 4 ) ( 3 4 )가 들어오게 되어 기대하는 정답은 3인데( 1,1,3이 담긴 우선순위 큐가 정답)

중간에 ( 2 5 ) 가 끼어들게 되면서 5를 끝점으로 잡고 3을 뺀 값 2보다 1이 작아서 우선순위 큐에 쌓아둔 1들이 전부 poll되는 이슈였습니다.

의도대로 돌아가게 하려면 1, 1 대신에 2가 나가고 3이 들어와야 하지만 튜플(2,5)로 인해서

1, 1이 나가고 2만 남게되는 상황이 발생하게 되면서 오답 처리됩니다.

 

 

 

3. 최종 코드

 

고친 코드의 문제는 sort의 방식에 있었습니다.  처음 투포인터 전략에서는 앞에서부터 사람들의 home을 기준으로 철로 D를 설치하면서 철로 안에 office 좌표가 들어오는 통근자들을 세어가서 튜플 0번째 인덱스를 기준으로 사람들의 통근 선분 원소들을 정렬하였습니다.

하지만 중간에 전략을 우선순위 큐로 수정하게 되면서 office를 기준으로 뒤에서 앞으로 D만큼을 측정하고 그 안에 들어오는 home들을 파악하게 되었으므로 정렬 또한 home을 기준으로 하지않고, office 기준으로 맞춰주어야 하는 이슈였습니다.

 

그래서 dis.sort()를 dis.sort(key=lambda x:x[1])로 변경해주었습니다.

 

최종 코드는 아래와 같습니다.

import heapq ,sys

a = int(sys.stdin.readline().strip())
dis = []
for i in range(a):
    h, o = map(int, sys.stdin.readline().strip().split())
    dis.append((min(h,o), max(h,o)))
dis.sort(key=lambda x:x[1])
d = int(input())

heap_arr = []
answer = 0

for i in range(a):
    if abs(dis[i][1]-dis[i][0]) <= d:
        heapq.heappush(heap_arr,dis[i][0])
        while heap_arr and heap_arr[0] < dis[i][1] - d:
             heapq.heappop(heap_arr)
        answer = max(answer, len(heap_arr))
print(answer)

시간 초과로 인해 투포인터 및 완전 탐색 대신에 우선순위 큐를 활용하여 철로에 들어오는 home 정보를 관리하고 뒷 원소인 office 기준으로 정렬을 해야했던 까다로운 문제였습니다. 

+ 추가 테스트

 

아래와 같이 순회 시에, if abs(dis[i][1]-dis[i][0]) <= d: 조건을 지워도 로직에 문제가 없어 백준 통과를 받을 수는 있지만 약간 느린 성능을 보여주었습니다. 다룰 필요없는 데이터는 최대한 우선순위 큐에 들어가지 않도록 하는 것이 조금이라도 시간을 단축시킬 수 있는 방법입니다.

import sys, heapq

a = int(sys.stdin.readline().strip())
arr = []
for i in range(a):
    h, o = map(int, sys.stdin.readline().strip().split())
    arr.append((min(h, o), max(h, o)))
arr.sort(key=lambda x:x[1])
d = int(input())
heaparr = []
answer = 0
for i in range(a):
    heapq.heappush(heaparr, arr[i][0])
    while heaparr and heaparr[0] < arr[i][1]-d:
        heapq.heappop(heaparr)
    answer = max(answer,len(heaparr))

print(answer)

 

아이디어 참고 :

https://blog.naver.com/occidere/221085858307