[프로그래머스/PYTHON] 정수 삼각형

프로그래머스 '정수 삼각형' 문제 풀이입니다.

 

문제 링크

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

● 문제 간단 설명

피라미드 모양으로 제시된 숫자 문자열이 있다.

가장 꼭대기에서부터 바닥으로 내려오는 경로 중에서 거쳐간 숫자의 합이 가장 큰 경로를 구하는 문제이다.

 

● 문제 해결 방향

다음 행에 대한 경로를 모두 구하도록 하고, 마지막 경로까지 갔을 때 합을 담고 있는 배열의 최댓값을 return 해주었다.

 

처음에는 다음 경로로 이동할 때 합이 가장 큰 곳으로만 이동하여 다른 경로에 대한 합을 구하지 않고 해결하려고 했다. 하지만 다음 경로로 이동할 때 두 경로의 값이 동일하면 그다음 행에 따라서 경로가 결정되기 때문에 이런 방식을 사용하지 않고,

전체 경로에 대한 각 최대값을 구하는 방향으로 코드를 작성하였다.

 

● 문제 해결 코드

def solution(triangle):
    answer = triangle[0]

    for row in triangle[1:]:
        new_answer = []

        for el, elIndex in zip(row, range(len(row))):
            if elIndex == 0:
                new_answer.append(answer[0] + el)
            elif elIndex == (len(row) - 1):
                new_answer.append(answer[-1] + el)
            else :

                if answer[elIndex] < answer[elIndex -1]:
                    new_answer.append(answer[elIndex - 1] + el)
                else:
                    new_answer.append(answer[elIndex] + el)

        answer = new_answer

    return max(answer)

우선 첫번째 행은 1개의 값만 가지기 때문에 초기 값으로 세팅해주었다.

 

2번째 행 부터 반복문을 실행하고, 다음 세 가지 경우에 대해서 다음 경로에 대한 숫자합을 구해주었다.

• 가장 왼쪽에 있는 경로
  다음 행의 0번째 값과 무조건 더해져야한다.
• 가장 오른쪽에 있는 경로
  배열 기준 -1번째 값과 무조건 더해져야 한다.
• 중간에 있는 경로
  왼쪽 경로의 숫자와 오른쪽 경로의 숫자의 크기 비교를 통해서 다음 경로를 결정해주었다.

중간 경로에 대해서 왼쪽 숫자 오른쪽 숫자의 크기 비교를 해주지 않으면 기존 삼각 배열의 행 길이와 일치하지 않게 돼버리기 때문에

크기 비교를 하여 그중 큰 숫자와 합한 값이 들어갈 수 있도록 해주었다.

 

반복문이 끝나면 마지막 행까지 오면서 더한 숫자들의 합계가 배열로 남게 된다.

따라서 마지막에는 max()를 통해 가장 큰 결과 값을 Return 해준다.

 

중간 결과 값을 출력하면 다음과 같이 나온다.

 

● 참고