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

정렬 + 스위핑 문제

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

2170번: 선 긋기

 

💡 풀이 코드

import sys
n = int(sys.stdin.readline())
line = []

for _ in range(n):
    start, end = map(int, sys.stdin.readline().split())
    line.append((start, end))

line.sort()

last = -sys.maxsize
answer = 0

for start, end in line:
    if last > start:
        if last < end:
            answer += (end - last)
            last = end
    else:
        answer += (end - start)
        last = end

print(answer)

 

👩🏻‍💻 위의 코드

나올 수 있는 경우의 수 : 총 3가지

⓵ 기존의 경우의 수와 완전히 겹치는 경우

⓶ 기존의 경우의 수와 겹치기도, 안겹치기도 하는 경우

⓷ 기존의 경우의 수와 완전히 안겹치는 경우

 

+ 우리는 line 배열을 첫번째 값인 start 기준으로 정렬해서 사용(같다면 두번째 값인 end 기준으로 정렬)하기 때문에 다음과 같은 경우는 고려할 필요가 없다.

• ⓵에서 2~3이 아닌 0~3인 경우 -> 이 경우엔 0~3인 경우가 for문을 가장 처음으로 돌 것.
• 즉, 우리는 항상 값을 정렬해서 사용하기 때문에 for문을 돌며 현재 end값이 가장 큰 경우에만 별도의 변수로 저장해주면 된다.