[BOJ][🟡5][백준#02170] 선 긋기

문제 출처

BAEKJOON Online Judge #2170

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자. 이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

예제

입력

4
1 3
2 5
3 5
6 7

출력

5

My Sol

import sys
input = sys.stdin.readline

N = int(input())
d = {}
for _ in range(N):
    s, e = map(int, input().split())
    v = d.get(s, 1e10)
    if v == 1e10 or v < e:
        d[s] = e

arr = sorted([(k, v) for k, v in d.items()])
ret = 0
tmps, tmpe = arr[0]

for s, e in arr[1:]:
    if tmpe < s:
        ret += tmpe - tmps
        tmps, tmpe = s, e
        continue

    tmpe = max(tmpe, e)

ret += tmpe - tmps
print(ret)

입력 처리

1. 딕셔너리를 이용해 시작점을 key로, 도착점을 value로 두었다.
2. 만약 입력에 해당하는 시작점이 이미 있었다면 더 긴 범위를 저장
3. 입력에 해당하는 시작점이 없었다면 해당 도착점을 저장해준다.
4. 모든 입력을 마치면 key 순으로 정렬해 값과 함께 arr 배열에 담아준다.

값 더하기

1. 기준 시작점과 도착점을 arr의 첫 배열로 둔다.
2. 만약 기준 도착점이 다음 조회하는 시작점보다 적다면 이어지지 않는 것이다.
3. 기준 시작점과 도착점의 길이를 ret에 더해주고 새로 맞이한 시작점과 도착점을 기준 시작점과 도착점으로 재설정한다.
4. 만약 기준 도착점이 다음 조회한 시작점을 넘어선다면 길이를 연장하거나 덮어씌울 수 있으므로 기준 도착점과 도착점 중 큰 값을 기준 도착점으로 설정한다.
5. 이 과정을 모두 거치면 ret에 현재 저장중인 기준 시작점과 도착점 간 거리를 더하고 출력한다.

결과

맞았습니다!!

모범답안

출처

from sys import stdin, stdout

N = int(stdin.readline())
line = [tuple(map(int, stdin.readline().split())) for _ in range(N)]
line.sort(key=lambda x:x[0])
ans = 0
limit = -1000000001
for i in range(N):
    if limit < line[i][0]:
        ans += line[i][1] - line[i][0]
        limit = line[i][1]
    elif limit < line[i][1]:
        ans += line[i][1] - limit
        limit = line[i][1]
stdout.write(f"{ans}")

큰 차이는 아니지만 메모리 사용이나 시간면에서 소폭 나은 코드를 분석해보려 한다. 비슷한 방법을 사용한 것 같다만 tuple을 사용했고, 중복을 걸러내지 않고 그냥 오름차순으로 정렬했다.

이후 limit을 갱신해나가며 길이를 매번 새로 더해가며 저장했다.