APCS Mar 2016 - b966 Q3 [Python]

문제 설명:

1차원 좌표축 위의 여러 선분이 덮는 전체 길이를 구합니다. 겹치는 부분은 한 번만 계산합니다. 예를 들어 선분 (5, 6), (1, 2), (4, 8), (7, 9)가 덮는 전체 길이는 아래 그림과 같이 6입니다.

def main():
    # 讀取線段數量
    n = int(input())

    segments = []

    # 讀取每個線段的起點和終點
    for _ in range(n):
        L, R = map(int, input().split())
        segments.append((L, R))

    # 將線段按照起點進行排序
    segments.sort(key=lambda x: x[0])

    # 合併線段
    covered_length = 0
    current_start, current_end = -1, -1

    for start, end in segments:
        if start > current_end:

            # 如果當前線段與前一線段不重疊，加上前一線段的長度(因為上一步不知道下一個是否比自己大)
            covered_length += current_end - current_start
            current_start, current_end = start, end
        else:
            # 如果重疊，延伸線段的結束點
            current_end = max(current_end, end)

    # 加上最後一個線段的長度
    covered_length += current_end - current_start

    # 輸出結果
    print(covered_length)


if __name__ == "__main__":
    main()
    

핵심 개념

• map 사용법: map(func, obj)

  예:

  map(int,input(),split())
  

• sort 사용법: [(배열)].sort(key=func)

  예:

  the_list = [(0,6),(3,8),(5,7),(2,5),(1,10),(8,12),(7,10)]
  the_list.sort(key= lamba x:x[0])
  

이 글은 번체 중국어 원문을 AI로 번역했습니다. 의미나 표현에 차이가 있을 수 있으니 정확한 내용은 번체 중국어 원문을 기준으로 확인해 주세요.