[백준] 2170번 : 선 긋기

2170번: 선 긋기

2170번: 선 긋기

🤔 문제분석

우선순위 큐로 문제를 해결하였는데, 그럴필요없이 한번의 순회로 문제를 해결할 수 있습니다.

우선순위큐로는 모든 큐를 순회하면서 연결 될 수 있는 조건을 연결하고, 연결하지 못한경우 원소를 추가합니다. 조금 더 생각해보니 모든 큐를 순회함으로 사실상 우선순위큐가 의미가 없다 🥲

한번의 정렬으로 해결 할 수 있는데 이전상태의 끝나는 점을 가지고 있다가 그 끝나는 점이 그다음 시작점보다 클경우, 작을경우, 같을경우 세가지의 상태로 분기시켜 문제를 해결 할 수 있습니다.

• 다음 시작점 > 끝나는점 : 새로운 길이가 추가 됩니다.
• 다음 시작점 == 끝나는점 : 새로운 길이가 추가됩니다.
• 다음 시작점 < 끝나는점 : 겹치는 경우임으로, 겹치는 부분을 제거해준뒤 길이를 더합니다. ( 다음끝나는점 - 끝나는점 )

💻 코드

처음 문제풀이

import sys
import heapq

input = sys.stdin.readline
N = int(input())

arr = []
for _ in range(N):
    start, end = map(int, input().split())
    arr.append((start, end))
    
arr.sort()

queue = []

heapq.heappush(queue, (arr[0][0], arr[0][1]))

for i in range(1, N):
    start, end = arr[i]
    
    new_queue = []
    
    is_added = False
    while queue:
        p_start, p_end = heapq.heappop(queue)
        if p_end >= start:
            is_added = True
            p_end = max(p_end, end)
            
        heapq.heappush(new_queue, (p_start, p_end))
        
    if not is_added:
        heapq.heappush(new_queue, (start, end))
        
    queue = new_queue
    
ans = 0    
for i in range(len(queue)):
    ans += queue[i][1] - queue[i][0]
    
print(ans)

이후 개선

import sys
input = sys.stdin.readline
N = int(input().rstrip())
arr = []
for _ in range(N):
    s,e = map(int,input().rstrip().split())
    arr.append((s,e))

arr.sort(key=lambda x : (x[0]))

tot = 0
max_check = -int(1e9)

for s,e in arr:
    if s > max_check: # 선분 개시
        tot += e-s
        max_check = e

    elif s <= max_check and e > max_check:
        tot += (e-max_check)
        max_check = e

print(tot)

🎯 피드백 및 개선사항

왜 왜 문제를 풀때에는 저런 아이디어를 떠올리지 못할까요… 😢 알고리즘의 갈길은 너무 머네요 !!