[백준] 2170번 선 긋기 - 파이썬(Python)

시간 제한 1초

문제 (링크)

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

2170번: 선 긋기

 

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
lines = []

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

lines.sort()

left = lines[0][0]
right = lines[0][1]
ans = 0

for i in range(1, n):
    if right >= lines[i][1]:
        continue
    
    elif lines[i][0] <= right < lines[i][1]:
        right = lines[i][1]
    
    elif right < lines[i][0]:
        ans += right - left
        left = lines[i][0]
        right = lines[i][1]

ans += right - left
print(ans)

코드 설명 및 풀이법

투 포인터와 유사한 방식의 알고리즘을 생각해냈다.

 

선들을 시작점 기준으로 오름차순으로 정렬한 후, 왼쪽과 오른쪽 포인터를 각각 첫 번째 선의 시작점과 끝점으로 잡는다.

 

앞서 말했듯, 선들은 시작점을 기준으로 오름차순으로 정렬되어 있기 때문에, lines[x-1]의 시작점은 절대 lines[x]의 시작점보다 클 수 없다.

 

따라서, 우리는 각 선이 끝나는 점만 비교해주면 된다.

 

선 두개가 겹치는지 확인하기 위해선, 더 먼저 오는 선이 끝나는 위치가 어디인지를 확인하면 쉽게 알 수 있다.

 

먼저 오는 선이 끝나는 위치는 세 가지로 구분할 수 있다.

 

해당 점을 X라고 하고, 두 번째로 오는 선의 시작점과 끝점을 각각 A, B라고 하자.

 

1) X가 B보다 크거나 같은 경우

- 이는 먼저 오는 선이 두 번째 선을 완전히 포함하고 있는 경우라고 할 수 있다.

Ex) (1, 10), (2, 5) or (1, 10), (2, 10)

 

이 경우, 두 번째 선은 고려할 필요 없이 그냥 1 ~ 10까지의 거리를 구해주면 두 선의 길이를 알 수 있다.

 

2) A <= X < B인 경우

- X가 A와 B 사이에 위치한 경우, 두 선은 겹쳐있는 것으로 생각할 수 있다. 따라서, 두 선의 총 길이는 첫 번째 선이 시작하는 곳에서 두 번째 선이 끝나는 곳까지의 거리가 된다.

 

Ex) (1, 5), (2, 7) -> 1 ~ 7까지의 거리

 

3) X가 A보다 작은 경우

- 두 선이 전혀 겹치지 않은 것으로 간주할 수 있다. 따라서, 두 선의 길이를 각각 구해준 후 더해주면 선들의 길이의 합이 된다.

Ex) (1, 2), (3, 4) -> 총 길이는 2

 

반복문을 돌면서 합칠 수 있는 선들은 합쳐주고, 합칠 수 없다면 지금까지 합쳐진 선의 길이를 ans에 더해주고, 그 다음 선의 시작점과 끝점을 각각 왼쪽, 오른쪽 포인터로 갱신해 작업을 반복해주면 된다.

 

시간초과?

사실, 이 문제를 풀 동안 시간초과를 참 많이 받았다.

그냥 내 코드가 뭔가 부족한가 생각도 했지만, 다른 사람들이 푼 코드와 시간복잡도 측면에서 차이가 없었고 정확한 이유도 모른채 다른 사람의 코드를 배끼긴 싫었다.

 

불행 중 다행으로 나와 동일한 문제를 겪는 사람이 있었고, 처음에 선들에 대한 입력값을 리스트가 아닌 튜플로 받으면 시간초과가 뜨지 않는다는 답변을 들을 수 있었다.

 

이 팁은 내 코드에도 성공적으로 적용됐다.

 

이런 경험이 처음이어서 리스트와 튜플 사이의 속도 차이를 검색해봤고, 리스트와 비교하여 튜플의 저장 속도 및 인덱싱 속도가 더 빠르다는 것을 알 수 있었다.

 

이 부분은 좀 흥미로워서 빠른 시일내에 정리해서 블로그에 포스팅해보려고 하겠다.