[프로그래머스] 2021 카카오 공채 - 정수 삼각형 (파이썬)

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

이번 문제는 deque를 사용하여 bfs 방식으로 풀어보았다. 하지만,, 이 문제를 한줄로 끝낸 정답을 보고 엄청난 현타가 왔지만, 어쨌든 한번 이번 문제에 대해서 설명해 보고자 한다. 

 

문제 설명

이번 문제는 삼각형 모양으로 숫자를 입력으로 받아 삼각형 꼭데기 숫자부터 지나가는 경로상의 숫자 합중 가장 큰 값을 찾아내는 문제이다. 위에서 내려올 때는 바로 밑에 두개 숫자로만 지나갈 수 있다.

풀이

queue를 만들어 bfs로 모든 경우 수를 돌리고, 층마다 DP를 만들어 그 위치까지의 최대값을 저장하고, 

마지막 4층에 도착하면 DP의 4층에 있는 값중 최대값을 뽑아내는 방식으로 구현하였다.

하는 동안에 효율성이 안나와서, 여러 방법으로 수정해 보았는데, 문제는 queue에 필요없는 데이터가 너무 많이 포함되어 시간이 오래걸렸었다. 현재는 x,y 두 가지 데이터만 돌렸었는데, 기존엔 Path, sum 등의 값들도 포함해서 계속 효율성이 안나왔었다.

코딩을 최적화 하기 위해서는 좀 더 논리적인 접근이 필요할 것 같다.

from collections import deque
def solution(triangle):
    l=len(triangle)
    move=[0,1]
    dp=[[-1]*i for i in range(1,l+1)]
    dp[0][0]=triangle[0][0] #sum
    x,y=0,0
    q=deque()
    q.append((x,y))
    while q:
        x,y=q.popleft()
        dx=x+1
        if dx >=l: continue
        for i in move:
            dy=y+i
            s=dp[x][y]+triangle[dx][dy]
            if dp[dx][dy] >= s: continue
            else : dp[dx][dy] = s
            q.append((dx,dy))
            if -1 not in dp[l-1]:
                return max(dp[l-1])

 

다른 사람 풀이 

아래 코드의 풀이 방식은  변수 'l'에 최대 경로 값을 넣어주고, 다음 단계로 넘어가며 생기는 가지를 양옆에 0인자를 넣어 문제를 해결하였다. 그리고 나는 최대 경로값을 2차원으로 삼각형 전체에 대해서 비교하였지만, 아래 코드는 필요한 그 층에 대한 최대 경로 값을 저장하여 효율성을 높였다.

solution = lambda t, l = []: max(l) if not t else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])

 

효율성 비교

왼쪽 코드 : 91.155ms /오른쪽 코드 : 24.647ms