[programmers] '겹치는 선분의 길이' 문제 해설 및 정답코드

 

문제 출처

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

프로그래머스

 

 

프로그래머스에서 제공하는 "겹치는 선분의 길이" 문제는 겉보기에 간단해 보여도, 막상 풀려고 하면 어디서부터 시작해야 할지 막막할 수 있습니다. 이 문서에서는 해당 문제를 누구나 이해할 수 있도록 차근차근, 그림을 머릿속에 그릴 수 있도록 설명해보겠습니다.

---

 

 

📌 문제 상황 이해하기

• 총 3개의 선분이 평행하게 놓여 있어요.
• 각 선분은 시작점과 끝점으로 구성된 배열로 주어집니다. 예: [0, 2]는 x축 위에서 0부터 2까지 이어진 선분입니다.
• 우리가 해야 할 일은? → "두 개 이상 선분이 겹치는 부분의 전체 길이를 구하라"입니다.

 

예시 입력:

lines = [[0, 2], [-3, -1], [-2, 1]]

 

이 선분들을 머릿속에서 쉽게 그려보려면 다음과 같이 선을 수평으로 펼쳐서 시각화해볼 수 있습니다:

좌표:   -3 -2 -1  0  1  2
선분 A:           ──┼──
선분 B:   ──┼──
선분 C:      ──┼──┼──

 

✔ 여기서 '──┼──'는 선분이 지나가는 좌표를 의미합니다. 겹치는 좌표에서는 여러 선분이 겹쳐 표시되므로 시각적으로 겹침이 어디 있는지 파악하기 쉽습니다.

 

정리해보면:

• 첫 번째 선분 [0, 2]는 좌표 0, 1을 포함합니다.
• 두 번째 선분 [-3, -1]은 좌표 -3, -2를 포함합니다.
• 세 번째 선분 [-2, 1]은 좌표 -2, -1, 0을 포함합니다.

 

➡ 겹치는 구간은 다음과 같습니다:

• 좌표 -2: 두 번째와 세 번째 선분이 겹침
• 좌표 0: 첫 번째와 세 번째 선분이 겹침

겹치는 좌표는 총 2개이므로, 정답은 2입니다.

---

 

📌 [start, end) 구간 표현 주의사항

여기서 주의할 점은 선분 [start, end]가 실제로는 start 이상, end 미만을 의미한다는 것입니다. 즉, start는 포함하고 end는 포함하지 않습니다.

예를 들어:

• [0, 2]는 좌표 0, 1을 포함하고, 2는 포함하지 않습니다.
• [-3, -1]은 좌표 -3, -2를 포함하고, -1은 포함하지 않습니다.
• [-2, 1]은 좌표 -2, -1, 0을 포함하고, 1은 포함하지 않습니다.

이것은 파이썬의 range(start, end)와 같은 규칙이며,

• 구간의 길이를 쉽게 end - start로 계산할 수 있고,
• 연속된 구간을 이어붙일 때도 편리합니다.

따라서 문제를 풀 때 항상 [start, end) 구간이라는 점을 염두에 두어야 합니다!

---

 

 

❓ 어떻게 풀 수 있을까?

이 문제는 복잡한 알고리즘 없이도 풀 수 있습니다. 좌표마다 선분이 몇 개 지나가는지를 직접 세어보면 됩니다.

해결 전략 요약

1. -100부터 100까지의 좌표를 담을 배열을 만든다 (총 201칸).
2. 각 선분이 지나가는 좌표 범위에 +1씩 표시한다.
3. 한 좌표라도 2개 이상 선분이 지나가면 "겹친다"고 간주한다.
4. 그런 좌표의 개수를 모두 더하면 "겹친 구간의 길이"가 된다!

---

 

 

🧮 구체적인 구현 방법과 해석

def solution(lines):
    points = [0] * 201  # -100부터 100까지 총 201개 좌표 준비

• 좌표값은 -100부터 100까지 존재할 수 있으므로, 총 201개의 배열 공간이 필요합니다.
• points[i]는 해당 좌표 지점을 선분이 몇 번 지나갔는지를 저장합니다.
• 예를 들어 points[100]은 실제 좌표 0에 해당합니다. (0 + 100 = 100)

 

    for start, end in lines:

• 주어진 세 선분 중 하나씩 꺼내서 start, end에 할당합니다.
• 예를 들어 lines = [[0,2], [-3,-1], [-2,1]]일 때, 첫 번째 반복에서는 start=0, end=2, 두 번째 반복에서는 start=-3, end=-1이 됩니다.

 

        for i in range(start, end):

• start부터 end 바로 전까지의 값을 i로 순회합니다.
• 예를 들어 start=0, end=2면 i=0,1이 됩니다.
• 중요한 점: range()는 끝값(end)을 포함하지 않는 [start, end) 형태입니다.

 

            points[i + 100] += 1  # 해당 좌표를 선분이 지나갔음을 표시하기 위해 1을 더함 (겹치는 횟수 누적)

• 음수 좌표를 배열 인덱스로 사용하기 위해 +100 보정을 합니다.
• 예: 실제 좌표 -2 → 인덱스 -2 + 100 = 98
• 해당 좌표를 선분이 지나간다고 표시하므로 +1을 해줍니다.
• 결국, 이 배열은 각 좌표에 선분이 몇 번 겹쳐졌는지를 저장하게 됩니다.

 

    # 겹치는 좌표 개수를 셉니다 (2개 이상 선분이 지나간 곳)
    overlap = 0                     # 겹치는 좌표 수를 저장할 변수 초기화
    for count in points:  # points 배열에서 각 좌표의 선분 겹친 횟수를 하나씩 꺼냄 (count는 그 횟수에 해당함)           # 각 좌표에 대해 선분이 몇 번 지나갔는지 확인
        if count >= 2:             # 두 개 이상의 선분이 지나갔다면
            overlap += 1           # 겹치는 구간으로 간주하고 1 증가시킴

    return overlap                 # 최종적으로 겹친 좌표의 총 개수를 반환

또는 아래와 같이 한 줄로 간결하게 쓸 수도 있습니다:

    return sum(1 for count in points if count >= 2)

• 조건을 만족하는 좌표마다 1씩 더해 바로 결과를 반환하는 간단한 형태입니다.
• points 배열을 전체 탐색하면서, 선분이 두 개 이상 겹친 좌표의 개수를 셉니다.
• count >= 2인 지점마다 1씩 더해서 최종적으로 겹친 전체 길이를 구합니다.

---

 

 

✅ 테스트 코드

if __name__ == "__main__":
    print(solution([[0, 2], [-3, -1], [-2, 1]]))     # 출력: 2
    print(solution([[0, 1], [2, 5], [3, 9]]))        # 출력: 2
    print(solution([[-1, 1], [1, 3], [3, 9]]))       # 출력: 0
    print(solution([[0, 5], [3, 9], [1, 10]]))       # 출력: 8

---

 

 

🧪 테스트 예제 요약

lines	겹치는 길이	설명
[[0, 1], [2, 5], [3, 9]]	2	[3, 5] 구간에 2개 겹침
[[-1, 1], [1, 3], [3, 9]]	0	겹치는 구간 없음
[[0, 5], [3, 9], [1, 10]]	8	[1, 9] 구간에서 항상 두 개 이상이 겹쳐 있음

---

 

💡 이 문제를 푼 후 꼭 기억해두면 좋은 것

• [start, end) 형식의 구간 표현 방식 → end는 포함하지 않아요!
• 좌표 범위가 작으면 직접 배열로 상태를 저장해 푸는 방식이 매우 강력합니다.
• 선분이 겹치는 문제는 카운팅 방식으로 접근하면 쉽게 해결됩니다.

---

 

 

✅ 결론

이 문제는 배열로 각 좌표의 상태를 기록하는 방법만 떠올릴 수 있다면, 어렵지 않게 해결할 수 있어요. 코드 자체는 짧지만, 처음 이 방식이 익숙하지 않다면 이해하는 데 시간이 좀 걸릴 수 있습니다. 따라서 그림을 머릿속에 떠올리며 구간을 하나하나 살펴보는 연습을 해보세요.

코딩 테스트에서도 자주 등장하는 유형이니 꼭 숙지해두시길 추천합니다!