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

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

프로그래머스

---

제출한 코드

def solution(lines):
    points = [0]*201
    
    for i in lines:
        x1, x2 = i[0]+100, i[1]+100
        for j in range(x1,x2):
            points[j] += 1

    answer = 0
    for i in points:
        if i >= 2:
            answer += 1

    return answer

풀이 요약

1. -100부터 100까지의 점을 담을 크기 201짜리 배열 points를 0으로 초기화한다.

2. 각각의 선분이 지나가는 점을 표시해준다: 배열의 (시작점+100) ~ (끝점+100)-1 번째 칸에 1씩 더해주기

3. 배열 값이 2를 넘어가면 선분이 2개 이상 그 점을 지나갔다는 뜻이므로 겹치는 부분이다 --> 이러한 점들을 카운트하여 리턴.

 

---

제출하고 다른 분들 코드를 보니까 그냥 집합으로 푼 사람들도 아주 많았다.

각 선분이 지나가는 점들을 각각 집합에 저장하고, 교집합 개수를 구해서 리턴.

다른 사람들 코드는 다 간단하고 멋진것같다.

---

여기서부터는 고민한 흔적들 기록.

 

처음에 생각했던 아이디어

 

1. lines에서 최소, 최대값 minVal, maxVal을 각각 찾는다

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]
minVal	minVal+1	minVal+2	minVal+3	minVal+4	minVal+5	minVal+6	minVal+7

이렇게 minVal ~ maxVal까지 숫자들을 담을 수 있는 배열을 만든다.

 

2. 각 선분이 해당 칸(점)을 지나감을 표현하기 위해서 처음 (시작점+1)~끝점까지 arr에 1을 더해준다.

 -예시. minVal=-1이고, [-1,3] 선분 표현

arr[0] (점 -1에 해당)	arr[1] (점 0에 해당)	arr[2] (점 1에 해당)	arr[3] (점 2에 해당)	arr[4] (점 3에 해당)
0	1	1	1	1

 -->선분 길이: 4

 

3. 3개의 선분에 대해 각각 2과정을 수행한다. 선분이 겹치는 점의 배열 값은 2 이상일 것이다.

    배열 값이 2보다 같거나 큰 점들을 모두 카운트하여 출력하면 된다.

 

이렇게 하려니까 배열 크기와 인덱스가 문제가 되었는지 자꾸 에러가 났고,

코드를 수정하려고 했더니 내가 짰는데도 인덱스 세는 게 자꾸 헷갈렸음.

 

마이너스 좌표를 어떻게 처리해야 하나 하다가 제일 작은 좌표를 배열의 맨 처음 값으로 두자 생각했던 거였는데,

 

고민하다보니까 조금 더 쉬운 방법이 있었다.

 

주어지는 점의 범위는 -100부터 100까지니까,

처음부터 크기 201짜리 배열을 만들어놓고, 숫자를 전부 다 100씩 오른쪽으로 밀어서 카운트하면 된다.

arr[0]	arr[1]	arr[2]	...	arr[100]	...	arr[201]
점 -100에 해당	점  -99에 해당	점 -98에 해당	...	점 0에 해당	...	점 100에 해당

 

즉, 좌표를 이렇게 100씩 오른쪽으로 밀어서 옮겨놓고,

편하게 카운트하면 되는거였당..... ^^...

 

어차피 주어진 a,b값이 -100에서 100으로 매우 작은 숫자들이기 때문에

minVal, maxVal 찾고 안 돌아가는 머리로 인덱스 설정하면서 시간 낭비 하는것보다

마이너스 좌표를 오른쪽으로 한번에 밀어버리는 방법을 사용할 때 훨씬 더 빠르게 문제를 풀어낼 수 있었다.