백준 문제풀이 - 2170 번

링크 -> https://www.acmicpc.net/problem/2170

1. 요약 및 풀이방법

이 문제는 선긋기로 유명한 문제입니다.
자를 대고 선을 긋는데 겹쳐서 그은 선은 구별이 안된다고 가정합니다.
Input으로는 N 개의 선, 그리고 각 N개 선의 양끝점의 x, y 좌표가 들어옵니다.

우선 x좌표를 기준으로 오름차순 정렬합니다.
이후 선이 도중에 끊어지지 않는 경우,
현재 겹쳐서 긋고 있는 선의 맨 앞과 맨 뒤 좌표를 갱신하여 저장하면서 진행합니다.

선이 끊어져서 겹쳐지지 않으면 현재까지 가지고 온 앞, 뒤 좌표로 현재 선의 길이를 누적 후,
맨 앞 점의 좌표를 새로 저장하여 다시 진행합니다.

2. Code

import sys

def main():
    N = int(input())
    lines = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
    lines.sort()

    length = 0
    cur_start = lines[0][0]
    cur_end = lines[0][1]
    for start, end in lines[1:]:
        if start > cur_end:
            length += (cur_end - cur_start)
            cur_start = start
        cur_end = max(cur_end, end)
    length += (cur_end - cur_start)

    print(length)

if __name__ == "__main__":
    main()

3. 학습 내용

알고리즘 자체는 단순하고 그다지 어려운 내용이 아닙니다.
다만 입출력 방식이 느리면 시간초과가 날 수 있어
input()이 아닌, sys.stdin.readline() 을 사용하였습니다.
이때 readline 함수는 맨 뒤의 \n 까지 같이 입력받으므로 주의해야 합니다.
위에서는 rstrip()으로 개행 문자를 제거했습니다.

4. 결과