[프로그래머스 - Level 2] 땅따먹기

[출처] : https://programmers.co.kr/

문제

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

 

입출력 예 설명

 

접근(1) - 속도가 더 빠른 풀이

문제에서 한 행씩 내려올때 같은 열을 연속해서 밟을 수 없다고 했고 최고점을 만들어 달라고 했다.

따라서 한 행씩 뽑고 다음 행의 0번째 열에는 1,2,3번째 열의 값의 최대값을 구해서 더해주었다

그렇게 되면 같은 열을 연속으로 밟는 경우가 안생긴다

이러한 방식으로 한행 한행 내려갈때마다 직전의 행에서 밟았던 열을 제외한 값들의 최대값을 더하게 되면 마지막 행에는 각 경로들의 점수들이 저장되게 된다

이중에서 최대값을 골라서 출력을 해주면 된다

def solution(land):
    answer = 0
    temp=0
    for i in range(len(land)):
        if i == len(land)-1:
            answer = max(land[i])
            break
        land[i+1][0] += max(land[i][1],land[i][2],land[i][3])
        land[i+1][1] += max(land[i][0],land[i][2],land[i][3])
        land[i+1][2] += max(land[i][0],land[i][1],land[i][3])
        land[i+1][3] += max(land[i][0],land[i][1],land[i][2])
        
    return answer

 

접근(2) - 속도는 상대적으로 느리지만 훨씬 깔끔한 풀이

이런식으로 반복되는 부분을 반복문을 이용해서 짧게 짤수도 있지만 일단 열이 4개밖에 없기도 하고

이와 같이 짜게 되면 시간이 더 오래걸린다.(max()도 시간복잡도 n을 갖기 때문에 훨씬 오래걸린다.)

결과를 비교해보면 약 1ms 만큼 더걸리는 것을 볼수있다.

만약 주어진 배열의 크기가 훨씬 컸다면 훨씬 더 오래걸렸을것이다.

def solution(land):
    answer = 0
    temp=0
    for i in range(len(land)):
        if i == len(land)-1:
            answer = max(land[i])
            break
        for j in range(len(land[0])):
            land[i+1][j] += max(land[i][:j]+land[i][j+1:])
        
    return answer