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

문제

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

프로그래머스

 

내 풀이 A

1. 겹치지 않게 모든 사람이 가위바위보 하는 방법을 응용해 2차원 배열 내 모든 좌표를 서로 비교한다.

2. 두 좌표 A, B의 시작, 끝 좌표에 대해 (시작:s, 끝: e)

    if A.e <= B.s or B.e <= A.s 이면 두 좌표는 서로 겹치지 않는다.

3. 겹친다면 A.s < B.e 상황에서 [A.s, B.e] 가 겹치게 된다.

4. 마찬가지로 elif B.s < A.e: [B.s, A.e] 

 

위에서 처음 생각한 방법으로 해보다가 만약 B가 A를 완전히 포함하여 길 경우 같은 상황에 대해 

고려하지 못했다는 것을 알았다.

 

내 풀이 B

그래서 문제상에서 가로로 좌표계를 두어 나타낸걸

세로로 세워 겹치는 부분을 알아내는 방법을 다시 생각해봤다.

[[0, 1], [2, 5], [3, 9]]				

		9
		8
		7
		6
	5	5    --------
	4	4    겹치는 부분
	3	3    --------
	2
1	
0

[[0, 2], [-3, -1], [-2, 1]]

2		
1		1	---
0		0	---
	-1	-1		===
	-2	-2		===
	-3

선분이 겹치는 부분의 길이 = 맨 위 - 맨 아래

def solution(lines):
    answer = 0
    result_arr = []
    # 1. 겹치지 않게 서로 악수
    # arr = [0, 1, 2, 3]
    # for i in range(len(arr)-1):
    #     for j in range(i+1, len(arr)):
    #         print([i, j])
    for i in range(len(lines)-1):
        for j in range(i+1, len(lines)):
            # print([lines[i], lines[j]])  # 서로 비교할 좌표 구했음
            # 2. 서로 겹치지 않는 좌표 제외
            A, B = lines[i], lines[j]
            if A[1] <= B[0] or B[1] <= A[0]:
                print(f'{A}와 {B}는 서로 겹치지 않는다.')
            else:
                # 3. 여기서 플랜 B로 진행했으나 이 방법도 아닌듯
                temp_arr = []
                for a in range(A[0], A[1]+1):
                    for b in range(B[0], B[1]+1):
                        if a == b:
                            temp_arr.append(a)
                result_arr.append(temp_arr)
                    
    print(result_arr)
    return answer

하지만 입력값 [[0, 5], [3, 9], [1, 10]]에 대해

[[3, 4, 5], [1, 2, 3, 4, 5], [3, 4, 5, 6, 7, 8, 9]]이 나오는것을 보고 이 방법도 일단 보류

 

내 풀이 C

def solution(lines):
    dict = {}
    for line in lines:
        # for e in range(line[0], line[1]+1):
        for e in range(line[0], line[1]):  // 아직도 헷갈리는 부분
            try:
                dict[e] += 1
            except:
                dict[e] = 1
    answer = 0
    for key in dict:
        if dict[key] > 1:
            answer += 1
    
    return answer

맨 처음 생각했던건 딕셔너리에 각각의 선분들이 지나가는 점에 대해 +1 해주고 

+2 이상인 점들의 개수를 리턴하는거였다.

근데 [0, 2], [1, 3]을 딕셔너리에 해보면 {0: 1, 1: 2, 2: 2, 3: 1}이 나올텐데

여기서 어떻게 겹치는 선분이 1만큼인걸 알 수 있을지에 대해 한참을 고민해봐도 알 수 없었다.

결국 주위에 물어보니 애초에 각 선분에 대해 맨 마지막 점이 없다고 생각하면 쉬워진다고 해서 

위 코드처럼 range를 돌게 했더니 정답이 나왔다.

아직까지 완벽히 이해되지 않지만 선분의 겹치는 길이를 구할 때는 맨 마지막 점을 빼줘야 한다는걸 기억하자

 

다른 풀이

def solution(lines):
    starts = [min(a) for a in lines]
    ends = [max(a) for a in lines]
    # print(starts, ends)
    starts.sort()
    ends.sort()
    # print(starts, ends)
    answer = 0
    answer += max(0, ends[0] - starts[1])
    answer += max(0, ends[1] - starts[2])
    answer -= max(0, ends[0] - starts[2])
    return answer

lines = [[0, 2], [-3, -1], [-2, 1]]
result = solution(lines)
print(result)

그나마 제일 알아보기 쉽게된 다른 풀이인데 

starts, ends로 answer에 왜 넣고 빼고 하고 있는건지 봐도 모르겠다..

나중에 다시 확인하자