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

 

프로그래머스

내 코드

def solution(lines):
    minmin = min(i for i, j in lines)
    maxmax = max(j for i, j in lines)

    overlap = [0] * (maxmax - minmin)

    for i, j in lines:
        for k in range(i, j):
            overlap[k - minmin] += 1

    answer = sum(1 for x in overlap if x >= 2)
    return answer

코드설명

• 선분 범위 계산: minmin과 maxmax는 주어진 lines 배열에서 선분의 시작점과 끝점 중 최소값과 최대값을 구합니다. 이렇게 해서 전체 선분을 포함할 수 있는 범위를 알 수 있습니다.
• 겹치는 부분 체크: overlap 배열은 선분이 겹치는 구간을 추적합니다. 배열의 각 인덱스는 선분의 하나의 구간을 나타내며, 해당 구간에 선분이 겹치면 값이 1씩 증가합니다.
• 겹치는 구간 계산: 마지막으로 overlap 배열에서 값이 2 이상인 구간을 찾아서 겹치는 부분의 길이를 구합니다.

특징

• 이 코드는 선분의 시작점과 끝점을 이용하여 선분을 포함하는 범위를 구하고, 그 범위 내에서 겹치는 구간을 추적하는 방식으로 동작합니다.
• 배열을 사용하여 선분의 겹침을 계산하고, 구간별로 겹친 부분을 체크하기 때문에 직관적이고 이해하기 쉬운 방법입니다.

---

다른 코드

def solution(lines):
    sets = [set(range(min(l), max(l))) for l in lines]
    return len(sets[0] & sets[1] | sets[0] & sets[2] | sets[1] & sets[2])

코드설명

• 선분을 집합으로 변환: 각 선분을 집합(set)으로 변환하여 해당 선분에 포함된 값들의 집합을 생성합니다. range(min(l), max(l))로 선분의 각 구간을 집합으로 만들고, 이를 sets 리스트에 저장합니다.
• 겹치는 부분 계산: sets[0] & sets[1] | sets[0] & sets[2] | sets[1] & sets[2]를 사용하여 세 선분의 겹치는 구간을 구합니다. 집합의 교집합(&) 연산자를 사용하여 겹치는 부분을 구하고, 그 길이를 계산합니다.

특징

• 이 코드는 집합(set)을 활용한 방법으로, 선분을 집합으로 표현하고 교집합 연산을 통해 겹치는 구간을 구합니다.
• 집합을 이용한 방법이므로 공백을 제외한 구간만을 고려하고, 선분이 겹치는 구간이 여러 번 나오는 경우를 자동으로 처리할 수 있습니다.

---

두 코드 비교

1. 배열 기반 접근: 내 코드는 배열을 이용하여 선분을 표현하고, 각 구간에 대해 겹치는 부분을 추적합니다. 이는 구간별 계산에 유리한 방식이며, 배열의 인덱스를 활용해 겹치는 부분을 체크할 수 있습니다.
2. 집합 기반 접근: 다른 코드는 **집합(set)**을 사용하여 각 선분을 집합으로 바꾸고, 교집합을 구하여 겹치는 부분을 계산합니다. 집합을 사용하면 중복된 값을 자동으로 처리할 수 있어 더욱 간결하게 구현할 수 있습니다. 그러나 교집합 연산을 여러 번 해야 하므로 연산이 다소 복잡할 수 있습니다.

---

결론

• 두 코드 모두 선분이 겹치는 구간을 계산하는 방식은 다르지만, 결과적으로 겹치는 부분의 길이를 계산하는 문제를 해결합니다.
• 배열을 사용하는 방법은 더 직관적이고 이해하기 쉽지만, 집합을 활용하는 방법은 코드가 더 간결하고, 집합 연산을 활용해 중복을 자연스럽게 처리할 수 있습니다.