[programmers/Swift] 땅따먹기

programmers.co.kr - 코딩테스트연습 - Lv.2 - 연습문제 - 땅따먹기

코딩테스트 연습 - 땅따먹기

Constraints :

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

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/05/08.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ land:[[Int]]) -> Int{
    var newLand = land

    for i in 1..<newLand.count {
        newLand[i][0] += max(newLand[i-1][1], newLand[i-1][2], newLand[i-1][3])
        newLand[i][1] += max(newLand[i-1][0], newLand[i-1][2], newLand[i-1][3])
        newLand[i][2] += max(newLand[i-1][0], newLand[i-1][1], newLand[i-1][3])
        newLand[i][3] += max(newLand[i-1][0], newLand[i-1][1], newLand[i-1][2])
    }

    return newLand[land.count - 1].max()!
}

print(solution([[1,2,3,5],
                [5,6,7,8],
                [4,3,2,1]])) // 16

How I tried this :
처음 풀이는 각 행을 방문하며 가장 큰 값들을 이어갔다.

하지만 이 경우는 틀렸다고 나온데다 시간이 오래걸려서 고민하고 관련 자료를 찾아보니

 

1. 내 풀이에는 문제가 있었다.

누적 점수의 최대값이 아니라 하나의 선택권만 주어지는 거기 때문에

4가지 루트의 각각의 경로를 모두 구해야 하는게 더 좋았다.

 

2. 직전 index를 체크하는 filter 과정

시간복잡도가 늘어나는 과정이여서 시간초과가 발생했다..

결국 0~4 index를 직접 작성해서 해당 시간을 줄임..

문제에 관한 모든 저작권 : https://programmers.co.kr/