[프로그래머스] Lv0_겹치는 선분의 길이

Lv0_겹치는 선분의 길이

📄Description

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.
lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.
선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

제한 조건

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

입출력 예시

lines	result
[[0, 1], [2, 5], [3, 9]]	2
[[-1, 1], [1, 3], [3, 9]]	0
[[0, 5], [3, 9], [1, 10]]	8

입출력 예 설명

1. 두 번째, 세 번째 선분 [2, 5], [3, 9]가 [3, 5] 구간에 겹쳐있으므로 2를 return 합니다.
2. 겹친 선분이 없으므로 0을 return 합니다.
3. 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
   첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
   두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
   따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.

---

🤔생각 정리

1. 중첩 for문으로 모든 조합을 구해야겠네
   (1, 2), (1, 3), (2, 3) - 3개니까 그냥 tuple로 해도 되겠다
2. 두 선분의 겹치는 길이를 계산해야겠네
   a와 b 선분의 겹치는 길이 = min(a2, b2) - max(a1, b1)
   값이 음수 -> 겹치지 않음 = 0

💡Pseudo Code💡

1. answer 초기화
2. for a in range(2):
3.		for b in range(a, 3):	
4.			line = a와 b 선분의 겹치는 길이 계산
5.			answer += line
6. return answer

---

🖥️코드화

def solution(lines):
    ans = 0
    for i, j in ((0,1),(0,2),(1,2)):
        a, b, = lines[i], lines[j]
        # 길이 < 0 -> 겹치지 않음 = 0
        ans += max(0, min(a[1], b[1])-max(a[0], b[0]))
    return ans

시행착오) 중복되는 길이는 제외해줘야하네

입출력 예3번에서 ([0, 5], [3, 9]) 2, ([0, 5], [1, 10]) 4,([3, 9], [1, 10]) 6로 총 12의 출력값을 얻었는데 결과는 8이다.

구간으로 보았을 때 겹치는 구간이 [3,5], [1,5], [3,9]이다. 총 겹치는 구간은 [1,9]로 8이 된다.
그러면 길이를 계산하는 것이 아니라 겹치는 좌표를 저장하면 될 것 같다.

def solution(lines):
    ans = []
    for i, j in ((0,1),(0,2),(1,2)):
        a, b, = lines[i], lines[j]
        # range 함수로 범위를 저장
        ans += list(range(max(a[0], b[0]), min(a[1], b[1])))
    return len(set(ans)) # 집합으로 변환해 중복 제거

---

📌코드 비교 및 감상

1. 집합의 합집합 & 교집합 활용
   나의 코드와 큰 틀은 비슷하지만 활용 방법에서 훨씬 깔끔한 것 같다.
   (1) 각 선분별로 좌표를 집합으로 저장한 후,
   (2) 선분 간의 교집합을 사용하여 겹치는 길이를 계산하고,
   (3) 합집합으로 중복을 제거한다.
   (나도 집합으로 중복을 제거하기는 했지만 합집합과 교집합을 활용하니까 훨씬 깔끔해보인다.)
   인용하자면 이렇다.

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])