[프로그래머스] 겹치는 선분의 길이 - Lv.0

프로그래머스 120876번 문제인 "겹치는 선분의 길이" Lv.0을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 겹치는 선분의 길이 Lv.0 - [파이썬/python]

 

 

프로그래머스-겹치는-선분의-길이

---

💻 문제 설명

 

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 반환(return) 하도록 solution 함수를 완성해보세요.

 

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

 

프로그래머스-겹치는-선분의-길이

 

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스

---

🚨 제한사항

 

• lines의 길이 = 3
• lines의 원소의 길이 = 2
• 모든 선분은 길이가 1 이상입니다.
• lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
  • -100 ≤ a < b ≤ 100

---

🌟 소스 코드

 

프로그래머스-겹치는-선분의-길이-파이썬-코드

 

 

def solution(lines):

   

    # 각 선분의 시작점과 끝점을 point로 만들어 리스트에 저장

    points = []

    for start, end in lines:

        points.append((start, 'start')) # 선분의 시작점을 'start' 타입의 point로 추가

        points.append((end, 'end')) # 선분의 끝점을 'end' 타입의 point로 추가

       

    points.sort() # 모든 point를 오름차순 정렬

   

    overlap_length = 0 # 겹치는 선분의 길이를 저장하는 변수

    overlap_count = 0 # 현재 겹치는 선분의 수를 저장하는 변수

    prev_point = None # 이전 포인트의 시간을 저장하는 변수

    # 모든 point를 순회

    for point, point_type in points:

       

        # 현재 겹치는 선분의 수가 2 이상이고 이전 point가 있으면,

        if overlap_count >= 2 and prev_point is not None:

           

            # 겹치는 선분의 길이에 (현재 point - 이전 point) 추가

            overlap_length += point - prev_point

           

        # point_type이 'start'이면 '겹치는 선분의 수'를 증가시키고, 'end'이면 감소

        if point_type == 'start':

            overlap_count += 1

        elif point_type == 'end':

            overlap_count -= 1

           

        # 현재 포인트(point)를 이전 포인트(pre_point)에 저장

        prev_point = point

    return overlap_length

 

 

---

⏱ 시간복잡도

 

위 코드의 시간 복잡도는 O(n log n)입니다.

 

 

- 정렬: points.sort()

선분의 시작점과 끝점을 정렬하는 데 O(n log n)의 시간이 소요됩니다. 정렬은 일반적으로 O(n log n)의 시간 복잡도를 가집니다.

 

- 루프: for point, point_type in points

모든 포인트를 순회하는 데 O(n)의 시간이 소요됩니다.

 

 

따라서, 전체 시간 복잡도는 정렬에 소요되는 시간(O(n log n))과 루프에 소요되는 시간(O(n))을 합한 것이므로, 최종적으로 O(n log n)이 됩니다.

 

이 방법은 모든 선분을 한 번씩 검사하므로, 선분의 수가 많아도 효율적으로 동작합니다.

 

 

---

🏳‍🌈 테스트 결과

 

프로그래머스-겹치는-선분의-길이-상태

 

프로그래머스-겹치는-선분의-길이-테스트-결과