[백준] 2170 선 긋기(Python)

문제 링크

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

나의 풀이

가장 핵심 로직은 겹치는 줄 들을 어떻게 합치느냐입니다.

예제 입력 중 (1,3), (2,5), (3,5)는 (1,5)로 합칠 수 있습니다.

합쳐지는 조건

1. 우선 주어진 입력들을 오름차순으로 정렬합니다.
2. 첫 번째 입력 좌표를 start, end변수로 설정합니다.
3. 두 번째 좌표부터 끝까지 탐색하며 합칠 수 있는지 살펴봅니다.
   1. 만약 i번 좌표의 시작점이 기존 좌표의 start <= lines[i][0] <= end이면 기존 줄과 합칠 수 있기 때문에 end변수를 갱신하고, 합쳐진 줄들의 좌표를 저장하는 combine_lines의 가장 마지막 인덱스의 1번 값을 end변수와 동일하게 갱신합니다.
      1. 이때, 무조건적으로 end좌표를 갱신하는 것이 아니라 기존 end와 i번 째 end 중 더 큰 값으로 갱신해야 합니다. ex) (1,6), (2,4)
   2. i번 째 좌표의 시작점이 기존 start보다 크다면 i번 째 줄은 새로운 줄로 판단하고 기존 줄의 start, end좌표를 저장한 뒤 start, end를 갱신합니다.
      1. 저는 combine_lines라는 리스트에 합쳐진 줄들의 좌표를 저장했습니다.

Code

# 선 긋기
# https://www.acmicpc.net/problem/2170

import sys
input = sys.stdin.readline

n = int(input())

lines = []
for _ in range(n):
    lines.append(tuple(map(int,input().split())))

lines.sort()
ans = 0

combine_lines = []

# 2. 첫 번째 입력좌표를 start, end변수로 설정
start = lines[0][0]
end = lines[0][1]
combine_lines.append([start,end])

is_add = False

for i in range(1,n):
    n_start = lines[i][0]
    n_end = lines[i][1]
    
    # 기존 줄과 합칠 수 있는 경우
    if start <= n_start <= end:
        combine_lines[-1][1] = max(combine_lines[-1][1], n_end)
        end = max(combine_lines[-1][1], n_end)
    
    # 기존 줄과 합칠 수 없는 경우
    elif n_start > end:
        combine_lines.append([n_start, n_end])
        start = lines[i][0]
        end = lines[i][1]

for start,end in combine_lines:
    ans += abs(end - start)

print(ans)

Git

https://github.com/youngh0/Algorithm/blob/master/greedy/boj_2170.py