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

문제

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

프로그래머스

선분 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

 

아이디어

꽤나 머리가 아팠다.

케이스를 나눠서 생각하기로 하고 하나하나 생각해보니 괜찮았다.

 

선분 1의 시작점이 선분 2의 끝점보다 크거나 같은 경우, 선분 1의 끝점이 선분 2의 시작점 보다 작거나 같은 경우 겹치는 선분은 없다.

 

선분 1의 시작점이 선분 2의 시작점보다 작거나 같은 경우 겹치는 선분의 시작은 선분 2의 시작점이 된다.

선분 1의 시작점이 선분 2의 시작점과 끝점 사이에 존재한다면 겹치는 선분의 시작은 선분 1의 시작점이 된다.

 

선분 1의 끝점이 선분 2의 끝점보다 작은 경우 겹치는 선분의 끝은 선분 1의 끝점이 된다.

선분 1의 끝점이 선분 2의 끝점보다 크거나 같은 경우 겹치는 선분의 끝은 선분 2의 끝점이 된다.

 

2개의 선분이 겹치는 구간을 찾는 것은 크게 2단계로 나누어 진행한다.

첫번째로 두 선분이 겹치는 구간을 저장한다.

두번째로 겹치는 구간사이가 2개 이상인 구간을 찾는다.

 

겹치는 길이가 중복된 경우를 고려해서 제거해야하는 것이 중요하다.

처음에 이걸 어떻게 해결할지 너무 머리가 아팠다.

레벨 0이 맞나.. ㅎㅎㅎ

중복제거에 유용하게 사용할 수 있는건 set이랑 dict인데 자연어처리를 하다보니 딕셔너리가 엄청 손에 익었다.

그래서 딕셔너리를 이용하여 겹치는 선분 조사.

겹치는 선분의 길이를 return해야 하기 때문에 끝나는 구간 -1 까지 조사해서 안에 포함된 숫자를 딕셔너리에 집어넣었다.

그러고 난 후 딕셔너리 전체의 len을 리턴하면 끝~

너무 힘든 문제였다..

나만 그런 걸까..?

노력하는 사람이 되자.

 

풀이

 

def solution(lines):
    answer = []
    answer.append(compare(lines[0], lines[1]))
    answer.append(compare(lines[0], lines[2]))
    answer.append(compare(lines[1], lines[2]))
    answer = [i for i in answer if i]
    if len(answer) == 0:
        return 0
    num = {}
    for i in range(len(answer)):
        for j in range(answer[i][0],answer[i][1]):
            if j in num:
                num[j]+=1
            else:
                num[j] = 1
    return (len(num))


def compare(a1, a2):
    start, end = 0, 0
    if a1[0] >= a2[1] or a1[1] <= a2[0]:    return 
    if a1[0] <= a2[0]:  start = a2[0]
    elif a2[0] < a1[0] < a2[1]: start = a1[0]
    if a1[1] < a2[1]:   end = a1[1]
    elif a1[1] >= a2[1]:    end = a2[1]
    return start, end