시간 제한 1초
문제 (링크)
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()
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에 더해주고, 그 다음 선의 시작점과 끝점을 각각 왼쪽, 오른쪽 포인터로 갱신해 작업을 반복해주면 된다.
시간초과?
사실, 이 문제를 풀 동안 시간초과를 참 많이 받았다.
그냥 내 코드가 뭔가 부족한가 생각도 했지만, 다른 사람들이 푼 코드와 시간복잡도 측면에서 차이가 없었고 정확한 이유도 모른채 다른 사람의 코드를 배끼긴 싫었다.
불행 중 다행으로 나와 동일한 문제를 겪는 사람이 있었고, 처음에 선들에 대한 입력값을 리스트가 아닌 튜플로 받으면 시간초과가 뜨지 않는다는 답변을 들을 수 있었다.
이 팁은 내 코드에도 성공적으로 적용됐다.
이런 경험이 처음이어서 리스트와 튜플 사이의 속도 차이를 검색해봤고, 리스트와 비교하여 튜플의 저장 속도 및 인덱싱 속도가 더 빠르다는 것을 알 수 있었다.
이 부분은 좀 흥미로워서 빠른 시일내에 정리해서 블로그에 포스팅해보려고 하겠다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준] 18808번 스티커 붙이기 - 파이썬(Python) (0) | 2021.10.12 |
---|---|
[백준] 1339번 단어수학 - 파이썬(Python) (1) | 2021.10.07 |
[백준] 1520번 내리막길 - 파이썬(Python) (0) | 2021.10.05 |
[백준] 2293번 동전 1 - 파이썬(Python) (3) | 2021.10.04 |
[백준] 2206번 벽 부수고 이동하기 - 파이썬(Python) (0) | 2021.10.03 |