[Swift] [21일차] 땅따먹기

핀·2024년 12월 28일

programmers swift

SwiftAlgorithm

목록 보기

24/105

Programmers-땅따먹기

문제 설명

N행 4열로 되어있고

연속되게 같은 열 못고름

막행까지 가면서 최댓값

문제 접근

각행 MAX 꼽아주면서 그때마다 이전이랑 같은 열인지만 판단해주면 될 듯 ??

초안인데, 이런식으로해서 town.index(of: MAxGround)!)를 lastIdx랑 비교해주면서 진행해주면 쉽게 풀릴 것 같다.

import Foundation

func solution(_ land: [[Int]]) -> Int {
    var answer = 0
    var lastIdx = 0
    for town in land {
        let maxGround = town.max()!
        print(town.index(of: maxGround)!)
    }
    return answer
}

개선

import Foundation

func solution(_ land: [[Int]]) -> Int {
    var answer = 0
    var lastIdx = -1
    for town in land {
        var maxGround = town.max()!
        var maxIdx = town.firstIndex(of: maxGround)!
        if lastIdx == maxIdx { // 같으면 그거 제외하고 다른 행에서 찾아야함
            var newTown = town
            newTown.remove(at: maxIdx)
            maxGround = newTown.max()!
            maxIdx = newTown.firstIndex(of: maxGround)!
        }
        answer += maxGround
        lastIdx = maxIdx
    }

    return answer
}

예제는 맞아서 제출을 돌렸더니 0점이 나왔다 (?)

뭔가 치명적인 결함이 있는 것 같은데, 예외케이스도 아니고.. 그래서 반례를 찾아보니

입력값 〉 [[6, 7, 1, 2], [2, 3, 10, 8], [1, 3, 9, 4], [7, 11, 4, 9]]
기댓값 〉 35
나의 출력 값 : 32

그니까 그냥 각항마다 바로바로 큰 값을 고려하는게 아니라, 그 다음꺼까지 고려해서 해줘야하는구나를 깨달았다. 각항마다 그때그때 큰값을 구하면서 열겹치는거만 피하면 32지만, 그 다음 행까지 고려를 해줘야하는거보니까 백트래킹 비슷하게 접근해야하는구나 싶어서 전면 수정에 들어갔다.

풀이 개선

import Foundation

func solution(_ land: [[Int]]) -> Int {
    var answer = 0
    func solve(rowIdx: Int, currentSum: Int, lastIdx: Int) {
        if rowIdx == land.count { // 마지막행 까지 봤으면 끝
            answer = max(answer, currentSum)
            return
        }
        for (idx, groundValue) in land[rowIdx].enumerated() {
            if idx != lastIdx { // 같은열 방지
                solve(rowIdx: rowIdx+1, currentSum: currentSum+groundValue, lastIdx: idx)
            }
        }
    }
    solve(rowIdx: 0, currentSum: 0, lastIdx: -1)
    return answer
}

lastIdx랑 겹치지 않는 애들로 전부다 재귀로 돌려줬는데, 이렇게하니까 전부 시간초과가 나왔다.
지난번 숫자변환에서 풀었던 것처럼 memo를 도입해보고자했다.

import Foundation

func solution(_ land: [[Int]]) -> Int {
    var memo = [[Int: Int]](repeating: [:], count: land.count)
    func solve(rowIdx: Int, lastIdx: Int) -> Int {
        if rowIdx == land.count { // 마지막행 까지 봤으면 끝
            return 0
        }
        if let memoValue = memo[rowIdx][lastIdx] {
            return memoValue
        }
        var maxSum = 0
        for (idx, groundValue) in land[rowIdx].enumerated() {
            if idx != lastIdx { // 같은열 방지
                maxSum = max(maxSum, groundValue + solve(rowIdx: rowIdx + 1, lastIdx: idx))
            }
        }
        memo[rowIdx][lastIdx] = maxSum
        
        return maxSum
    }
    return solve(rowIdx: 0, lastIdx: -1)
}

MEMO

메모 배열을 최종에 찍어보면
[[-1: 35], 
[1: 28, 2: 28, 3: 25, 0: 28], 
[2: 15, 3: 20, 0: 20, 1: 20], 
[0: 11, 1: 9, 3: 11, 2: 11]]
이런식으로 찍히는데, 이게
memo[rowIdx][lastIdx]의 뜻이 해당 행에서 lastIdx를 못고른다면 앞으로 최댓값이 이거입니다! 하고 알려주고 있는 것이다.

정확성: 59.8

효율성: 0.0
합계: 59.8 / 100.0
정답은 다 맞았는데 효율성 테스트에서 전부 시간초과가 떴다..

시간초과 한 번 더 개선

이쯤 되니까 진짜 쌩DP로 크게 생각안하고 풀어야하나? 싶었다.
이게 어처피 줄로 정해져있으니까 현재 인덱스 안겹치려면 +한다음에%4해주면 겹치지 않을 것이라서, 그쪽 방향으로 풀고 memo에 적어주는 방식으로 구성했다.

완성 코드

import Foundation

func solution(_ land: [[Int]]) -> Int {
    let LEN = land.count
    var memo = land

    for i in 1 ..< LEN {
        for lastIdx in 0 ..< 4 {
            memo[i][lastIdx] += max(
                memo[i-1][(lastIdx+1)%4],
                memo[i-1][(lastIdx+2)%4],
                memo[i-1][(lastIdx+3)%4]
            )
        }
    }
    return memo[LEN-1].max()!
}

MEMO 프린트 찍으면?

[[6, 7, 1, 2], [9, 9, 17, 15], [18, 20, 24, 21], [31, 35, 25, 33]]

이렇게 memo = land 된거에서 누적값을 계속 더해주면서하니까 굳이 코드가 길어질 필요가 없었다.

채점 결과

정확성: 59.8
효율성: 40.2
합계: 100.0 / 100.0

타인의 코드

import Foundation

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

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

    return new_land.last!.max()!
}