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

프로그래머스

 

코드

def solution(lines):
    answer = 0
    count = [0 for _ in range(200)] # -100 ~ 100 까지의 범위에서 해당 점에 선분이 그어진 횟수
    for line in lines:
        for i in range(line[0], line[1]): 
            count[i + 100] += 1
    answer += count.count(2) # 두 개 이상 겹친 점
    answer += count.count(3) # 세 개 이상 겹친 점
    return answer

그림과 같이 세 선분이 그려져 있을 때, 두 개 이상의 선분이 겹치는 부분의 길이를 구하는 문제이다.

위 그림에서 두 개 이상의 선분이 겹치는 부분은 [-2, -1], [0, 1]으로, answer는 2가 된다.

 

처음에는 세 선분의 시작점과 끝점을 조건문으로 비교하여 겹치는 부분의 길이를 answer에 더하는 방식으로 코드를 작성했다.

하지만 세 선분이 겹치게 되면 세 선분이 모두 겹치는 부분을 answer에서 빼줘야 하는 상황이 발생하기 때문에 세 선분이 겹치는 부분의 길이를 구하기 어려웠다.

그래서 어떻게 하면 겹치는 부분인 지 체크할 수 있을지 생각해 보다, 해당 점에 선분이 지나가는 횟수를 체크하면 가능할 것 같았다.

 

그래서 count라는 리스트를 만들었다. 이 리스트는 -100부터 100까지의 점에 선분이 그어진 횟수를 체크한다.

-100부터 100까지의 점이라는 말이 문제를 해결하는데 조금 껄끄러운 부분이 있다.

선분이기 때문에 [0,1]이면 0에도 +1, 1에도 +1을 해주어야 하는데, 이렇게 체크하면 0과 1 사이의 구간에 선분을 그은 것인데 점과는 의미가 조금 달라진다.

그래서 이 부분은 [0,1]이면 0에 +1을 하는데, 이때 0.5라는 점에 체크를 한다고 바라보면 조금 이해하기가 쉬울 것이다.

0과 1을 잇는 선분이라는 것은 0.5를 지나가고 있기 때문에 모든 선분들을 0.5 단위로 체크를 하는 것이다.

=> 0번 인덱스 = 0.5, 1번 인덱스 1.5, 2번 인덱스 2.5... 

이런 식으로 코드를 바라봐주길 바란다.

 

이제 lines에 담긴 요소들로 반복문을 돌린다. lines에서 구간을 하나씩 가져와 시작점에서 끝점까지 반복해서 count에 +1을 한다.

그림에서 주어진 점인 [-3, -1] [-2, 1], [0, 2]를 가지고 과정을 설명하면 다음과 같다.

1) [-3, -1] -> count[ -3 + 100 ] , count[ -2 + 100 ]에 각각 +1
2) [-2, 1] -> count[ -2 + 100 ], count[ 1 + 100 ]에 각각 +1
3) [0, 2] -> count[ 0 + 100 ], count[ 2 + 100 ]에 각각 +1

인덱스에 +100을 해주는 이유는 리스트가 0번부터 시작하기 때문이다.

우리는 -100부터 100까지의 범위를 가지고 있다. 그러기 때문에 0번 인덱스가 -100이라는 점을 의미하는 것이다. 그러므로 좌표값+100을 해주는 것이다.

 

모든 count 과정이 끝나면 count에 2와 3이 총 몇 개 있는지 세주면 된다.

count() 함수를 이용하여 두 개의 선분이 겹친 경우(=2)와 세 개의 선분이 겹친 경우(=3)를 answer에 더해주면 두 개 이상의 선분이 겹친 구간의 길이를 알 수 있다.

 

나는 인덱스로 접근해서 풀었지만, 다른 사람들의 코드를 보니 집합을 이용하여 푼 코드가 깔끔해보여서 살펴보고 다시 글을 추가해서 작성해야겠다!!