[프로그래머스] 정수 삼각형 (python)

- 5월 05, 2021

문제설명

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43105

Idea

문제의 조건을 보면 "꼭대기에서 바닥까지 이어지는 경로 중, 숫자 합이 가장 큰 경우"를 찾는 문제입니다.

2차원 리스트가 주어졌을 때 모든 경우의 수를 계산 해야만 숫자 합이 가장 큰 경우를 찾을 수 있습니다.

리스트의 합을 구하는 조건은 "한 칸 오른쪽"과 "한 칸 왼쪽"으로 갈 수 있다고 정의되어 있습니다.

이는 triangle[0][0]에 있는 값은 triangle[1][0]과 triangle[1][1]로 갈 수 있고,

triangle[2][1]은 triangle[3][1]과 triangle[3][2]로 갈 수 있다는 의미입니다.

숫자의 가장 큰 합을 구해야하기 때문에 triangle[1][0]에는 triangle[0][0]+triangle[1][0]을 해주면 되고,

triangle[3][1]은 triangle[3][1] + triangle[2][0] 또는 triangle[3][1] + triangle[2][1] 중 큰 값을 넣으면 됩니다.

이는 triangle[i][j] + triangle[i-1][j]와 triangle[i][j] + triangle[i-1][j+1] 중 큰 값을 triangle[i][j]에 넣어주면 됨을 유추할 수 있습니다.

Solution 01

from copy import deepcopy
def solution(triangle):
    # 0.298445245
    triangle_temp = deepcopy(triangle)
    max_sum = triangle[0][0]
    for i in range(1, len(triangle)):
        for j in range(i):
            if triangle[i][j] < triangle_temp[i][j] + triangle[i-1][j]:
                triangle[i][j] = triangle_temp[i][j] + triangle[i-1][j]
            if triangle[i][j+1] < triangle_temp[i][j+1] + triangle[i-1][j]:
                triangle[i][j+1] = triangle_temp[i][j+1] + triangle[i-1][j]
            if max_sum < triangle[i][j]:
                max_sum = triangle[i][j]
            if max_sum < triangle[i][j+1]:
                max_sum = triangle[i][j+1]
    return max_sum

제한 사항에서 숫자는 0이상 9999이하라는 조건을 놓쳐 음수가 있다고 가정하였습니다.

max_sum을 생성한 뒤 행마다 값의 합을 구하여 최댓값을 max_sum에 저장했습니다.

Solution 02

from copy import deepcopy
def solution(triangle):
    triangle_temp = deepcopy(triangle)
    for i in range(1, len(triangle)):
        for j in range(i):
            if triangle[i][j] < triangle_temp[i][j] + triangle[i-1][j]:
                triangle[i][j] = triangle_temp[i][j] + triangle[i-1][j]
            if triangle[i][j+1] < triangle_temp[i][j+1] + triangle[i-1][j]:
                triangle[i][j+1] = triangle_temp[i][j+1] + triangle[i-1][j]
    return max(triangle[-1])

trianlge에 주어진 값은 모두 양수이니, 마지막 행의 최댓값을 구하면 "삼각형 꼭대기부터 바닥"의 최댓값을 구할 수 있습니다.

Solution 03

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][0] += triangle[i-1][0]
            elif j == i:
                triangle[i][-1] += triangle[i-1][-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    return max(triangle[-1])

Solution 02에선 매번 [i][j] + [i-1][j]와 [i][j] + [i-1][j+1] 값을 각각 구하여 triangle[i][j]에 더 큰 값을 할당하고 있습니다.

매번 [i-1][j]와 [i-1][j+1] 값을 더하여 더 큰 값을 할당하는 방법 대신,

맨 왼쪽 값은 무조건 이전 리스트의 0번을 더해야하고, 맨 오른쪽 값은 이전 리스트의 끝번을 더해야하기 때문에 이에 대한 예외처리를 if문으로 잡았습니다.

이후 [i-1][j-1]과 [i-1][j] 중 큰 값을 먼저 찾은 다음 [i][j]에 더해주는 방식으로 효율성을 증진했습니다.

Solution 04

def solution(triangle):
    l = []
    for r in triangle:
        l = [max(t, y) + z for t, y, z in zip([0]+l, l+[0], r)]
    return max(l)

마지막으로 Solution 03에서 맨 왼쪽과 맨 오른쪽을 각각 예외처리하는 대신,

[0]을 맨 왼쪽과 맨 오른쪽에 각각 추가하여 [i-1][j-1]과 [i-1][j] 중 큰 값을 찾아 [i][j]에 더해주는 방식입니다.

맨 처음 r은 7이고 l = []이니, zip([0], [0], [7])이 되며 이는 max(0, 0) + 7로 l=[7]이 됩니다.

그 다음 r은 [3, 8]이고 l=[7]이니, zip([0, 7], [7, 0], [3, 8])이 되고 [max(0, 7)+3, max(7, 0)+8]으로 [10, 15]을 계산하는 방식입니다.

전체 코드는 깃허브에서 확인 가능합니다.

이 블로그 검색

프로그래밍 관련 정보