[Boj/백준] 2170 Python

문제출처: https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

 

1. 문제 접근 방식

스위핑 알고리즘을 19598 최소 회의실 개수 문제처럼 풀었다.

x와 y가 작은 순서대로 lambda를 이용해 sorting을 하고 end와 cur를 잡고

각각 원소와 비교해가며 바꿔갔다.

처음에 틀렸었는데

5 10

7 35

20 25

이렇게 두번째 원소의 y가 그 다음 원소의 y보다 클 경우도 고려해서 풀었다.

 

 

2. 내가 푼 코드

import sys

case = int(sys.stdin.readline())
arr = []

for _ in range(case):
    n,m = map(int,sys.stdin.readline().split())
    arr.append((n,m))

arr.sort(key=lambda x:(x[0],x[1]))
result = 0
cur = arr[0][0]
end = arr[0][1]
for i in range(len(arr)-1): #0 1 2
    if end < arr[i+1][0]:
        result+=end-cur
        cur = arr[i+1][0]
        end = arr[i+1][1]
    if end >= arr[i+1][0]:
        if end < arr[i+1][1]:
            end = arr[i+1][1]

result+=end-cur

print(result)

 

 

3. 결과 및 느낀점

스위핑 문제도 정렬과 함께 자주 나오는 것 같다.

순환하면서 cur과 end값을 잘 바꿔나가자.

반례도 항상 생각해볼것