[BaekJoon] 백준 2170 선 긋기

[BaekJoon] 백준 2170번 선 긋기

 

🎈문제

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

💬설명

• 스위핑 기법으로 푸는 문제라고 한다.스위핑 기법이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보면 된다.
• 풀이 과정
  1. 시작점을 기준으로 sort한다.
  2. 다음 line이 이전 line에 포함되는 경우, 일부가 겹치는 경우, 아예 겹치지 않는 경우 이렇게 3가지로 나눠서 생각한다.
• 주의
  • 데이터의 크기가 큰만큼 시간초과가 계속 났다.
  • 해결책
    1. import sys -> input = sys.stdin.readline
    2. arr 속에 line들을 tuple로 저장 (iteration 도는 속도가 tuple이 빠르다고...?)
    3. pypy로 채점

👩‍💻코드

# BaekJoon2170.py
import sys


input = sys.stdin.readline
N = int(input())
arr = []
for i in range(N):
    arr.append(tuple(map(int, input().split())))
arr.sort()
start = arr[0][0]
end = arr[0][1]
result = 0

for i in range(1, N):
    # 겹치는 경우
    if arr[i][0] <= end < arr[i][1]:
        end = max(end, arr[i][1])

    # 겹치지 않는 경우
    elif arr[i][0] > end:
        result += end - start
        start = arr[i][0]
        end = arr[i][1]

result += end - start

print(result)

👉참고

https://blog.naver.com/kks227/220907708368