코딩테스트입문 / 겹치는 선분의 길이

📚문제

출처 : 프로그래머스 / 겹치는 선분의 길이(https://school.programmers.co.kr/learn/courses/30/lessons/120876)

 

📝풀이

# 처음 코드
def solution(lines):
    
    num_list = [k for i in lines for k in range(i[0],i[1]+1)]
    result = [ j for j in num_list if num_list.count(j)>=2 ]
    return len(set(result))-1

# 두 번째 코드
def solution(lines):

    num_list = [k for i in lines for k in range(i[0],i[1]+1)]
    result = [ j for j in num_list if num_list.count(j)>=2 ]

    for i in range(1,len(result)):
        result = list(result)
        if result[i] == result[i-1]+1:
            return len(result)-1
            break
        else:
            return 0

1. 첫 번째 코드

선분이 포함되는 영역의 숫자들을 리스트로 만든 후에

겹치는 부분의 값을 return했다

이렇게 작성하면서 몇 번 실패를 거듭했는데 그 이유는

 

두 번째 예시([[-1,1],[1,3],[3,9]])처럼 선분이 꼭지점에서 겹쳐있는 경우는

세지 말아야 하는데 카운트를 하게된다

 

2. 두 번째 코드

그래서 최종결과값이 연속되게 나오지 않는다면 꼭짓점이라고 간주하고 

그 결과값은 세지 않는 코드를 만들어보았다

 

근데 이렇게 코드를 작성하면

만약에 두번째 예시가

([[-1,1],[1,3],[2,9]])

이런 경우라면

처음 두 선분은 꼭짓점에서 겹치는데도 결과값들이 연속되어 나오기 때문에 

이 값이 포함되게 된다

 

그러다가 다른 분의 코드를 보고 힌트를 얻어 내 코드를 조금 수정해서 답을 만들었다

# 세 번째 코드
num_list = [k for i in lines for k in range(i[0],i[1]+1)]

코드의 이 부분에서 끝 범위에 +1을 해주어야 한다고 생각했다

선분을 그려야하는 거라면 모든 값을 포함해주는게 맞지만
겹치는 부분을 찾는것이므로 끝에 부분을 제외시켜 주는게 맞는 것이다.

조금 더 이해하기 쉽게 그림을 그려보면

문제에서 준 두 번째 예시로 선분을 그려본다면 원래는 이렇게 그려지는게 맞다

근데 겹치는 부분을 찾는 문제이므로 이렇게 모든값을 포함하게 되면 (1,3)에서처럼

실제로 겹치지 않는데 값이 중복되어 들어간다

 

따라서 이 그림처럼 끝의 부분을 포함시키지 않게 되도

겹치는 부분이 있다면 값이 잘 중복되어 들어갈 수 있다

(지금은 겹치는 부분이 없으므로 0이 나옴)

 

# 최종 코드
def solution(lines):
    num_list = [k for i in lines for k in range(i[0],i[1])]
    result = [ j for j in num_list if num_list.count(j)>=2 ]
    return len(set(result))

 

 

 

+ 참고한 코드 💁‍♂️

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