[프로그래머스] Lv.2 땅따먹기 (Swift) 문제풀이

Cobugi·2022년 4월 5일

swift 알고리즘

알고리즘

목록 보기

10/11

프로그래머스 Lv.2 땅따먹기

요약

문제에서의 조건은 위에서 지나갔던 열을 다시 갈 수 없다는 것이다
- 예를 들어, [1,2,3,5]에서 1을 지나갔다면 다음 행인 [5,6,7,8]의 5는 지나갈 수 없다
이를 거꾸로 생각해보자
- 다음 행인 [5,6,7,8]의 5로 올 수 있는 수는 [2,3,5]이다
- 그렇다면 5까지 왔을 때 최댓값은 [2,3,5]에서 최댓값을 5에 더해주면 된다
예를 들어
- [1,2,3,5], [5,6,7,8], [4,3,2,1] 순으로 주어졌을 때
- [5,6,7,8]까지의 최댓값들을 구할 것이다
  - 5까지의 최댓값은 5 + [2,3,5].max()! => 10
  - 6까지의 최댓값은 6 + [1,3,5].max()! => 11
  - 7까지의 최댓값은 7 + [1,2,5].max()! => 12
  - 8까지의 최댓값은 8 + [1,2,3].max()! => 11
- 따라서 2번째 행([5,6,7,8])까지 오는데 최댓값들은 [10,11,12,11]이다
- 그 다음으로 [4,3,2,1]까지의 최댓값들을 구할 것이다
  - 4까지의 최댓값은 4 + [11,12,11].max()! => 16
  - 3까지의 최댓값은 3 + [10,12,11].max()! => 15
  - 2까지의 최댓값은 2 + [10,11,11].max()! => 13
  - 1까지의 최댓값은 1 + [10,11,12].max()! => 13
- 최종적으로 [16,15,13,13]이 나오는데 이 배열의 최댓값을 반환하면 된다

설명

두 배열을 비교하여 2번째 행의 배열에까지의 최댓값들의 배열을 구하자

func compareArr(arr1: [Int], arr2: [Int]) -> [Int] {
    var arr2 = arr2
    let arrs = [
        [arr1[1], arr1[2], arr1[3]],
        [arr1[0], arr1[2], arr1[3]],
        [arr1[0], arr1[1], arr1[3]],
        [arr1[0], arr1[1], arr1[2]]
    ]
    for i in 0...3 {
        arr2[i] += arrs[i].max()!
    }
    return arr2
}

첫번째 행을 현재 갈 수 있는 최댓값들의 배열이라고 하고, 두번째 행 부터 비교하여 현재 갈 수 있는 최댓값들의 배열을 갱신해주면 된다

import Foundation

func solution(_ land: [[Int]]) -> Int {
    var current = land[0]
    for i in 1..<land.count {
        current = compareArr(arr1: current, arr2: land[i])
    }
    
    return current.max()!
}

전체 코드

import Foundation

func solution(_ land: [[Int]]) -> Int {
    var current = land[0]
    for i in 1..<land.count {
        current = compareArr(arr1: current, arr2: land[i])
    }
    
    return current.max()!
}

func compareArr(arr1: [Int], arr2: [Int]) -> [Int] {
    var arr2 = arr2
    let arrs = [
        [arr1[1], arr1[2], arr1[3]],
        [arr1[0], arr1[2], arr1[3]],
        [arr1[0], arr1[1], arr1[3]],
        [arr1[0], arr1[1], arr1[2]]
    ]
    for i in 0...3 {
        arr2[i] += arrs[i].max()!
    }
    return arr2
}

결과

정확성

테스트케이스	결과
테스트 1	통과 (2.22ms, 16.8MB)
테스트 2	통과 (4.01ms, 16.8MB)
테스트 3	통과 (2.11ms, 16.9MB)
테스트 4	통과 (2.22ms, 16.7MB)
테스트 5	통과 (2.23ms, 16.6MB)
테스트 6	통과 (2.22ms, 16.6MB)
테스트 7	통과 (2.07ms, 16.8MB)
테스트 8	통과 (3.27ms, 16.7MB)
테스트 9	통과 (2.13ms, 16.5MB)
테스트 10	통과 (3.94ms, 16.9MB)
테스트 11	통과 (2.24ms, 16.6MB)
테스트 12	통과 (2.93ms, 16.6MB)
테스트 13	통과 (3.15ms, 16.7MB)
테스트 14	통과 (4.55ms, 16.9MB)
테스트 15	통과 (2.31ms, 16.7MB)
테스트 16	통과 (2.23ms, 16.5MB)
테스트 17	통과 (2.12ms, 16.8MB)
테스트 18	통과 (2.23ms, 16.8MB)