(Python3) - 프로그래머스(코딩테스트 입문) : 겹치는 선분의 길이

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

프로그래머스

n이 작은 sweeping문제였습니다

📕 풀이방법

📔 입력 및 초기화

1. 정답 변수 answer 선언 후 0으로 초기화합니다.

 

2. 합쳐진 구간 overlap 선언 후 빈 배열로 초기화합니다.

📔 풀이과정

좌표	1	2	3	4	5	6	7	8	9
Segment x		■	■	■	■	■
Segment x2				■	■	■	■	■
Overlap				★	★	★

 

* 겹치는 길이만 구하면되므로 해당 선분들을 모두 압축해서 하나로 만든다고 생각하면 구현하기 수월할 수 있습니다.

 

lines에 대해 2차원 for loop를 수행하며 

1. x[1] <= x2[0]이면서 x[0] <= x2[1]인 선분이 존재하는 경우 겹치는 부분만 overlap에 추가해줍니다.

 

2. 겹치는 부분이 없는 경우 0을 반환합니다.

 

3. x에 대해 오름차순. 같다면 y에 대해 오름차순으로 정렬해줍니다.

 

4. 현재 start와 end를 선언 후 overlap의 첫 번째 값을 저장합니다.

 

5. 1부터 overlap의 원소를 순회하며 다음을 진행합니다.

  5-1. 다음 겹치는 구간의 지역변수 start, end선언 후 해당 값을 저장합니다.

  5-2. 다음 구간이 현재의 끝 점 이하라면 겹치는 부분이 길어지므로 현재의 끝점을 다음 선분의 끝점으로 연장시켜줍니다. 아니라면 answer에 현재 처음과 끝 점을 더해주고 다음 구간으로 현재 구간을 갱신해줍니다.

6. 마지막으로 겹치는 구간을 구해 answer에 더해줍니다.

📔 정답 출력 | 반환

answer를 반환합니다.

---

📕 Code

📔 Python3

def solution(lines):
    answer = 0
    overlap = []
    
    for i, x in enumerate(lines):
        for j, x2 in enumerate(lines):
            if i == j:
                continue
            if x2[0] <= x[1] and x[0] <= x2[1]:
                min_val = max(x[0], x2[0]) 
                max_val = min(x[1], x2[1]) 
                overlap.append([min_val, max_val])
    
    if not overlap:
        return 0
    
    overlap.sort()
    
    current_start, current_end = overlap[0]
    for i in range(1, len(overlap)):
        start, end = overlap[i]
        if start <= current_end:
            current_end = end
        else:
            answer += current_end - current_start
            current_start, current_end = start, end
    
    answer += current_end - current_start
    return answer

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.