프로그래머스 땅따먹기 Swift

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

풀이:

이 문제의 핵심은 현재 행의 숫자 4개에 현재 열을 제외한 바로 전 행 숫자 중 가장 큰 숫자를 더해서 가장 큰 값을 현재열 값으로 바꿔나가는 것입니다.

 

이렇게 말하면 이해하기가 어렵기 때문에 예를 들면서 설명하겠습니다.

문제의 예와 같이 첫번째행 [1,2,3,5] 두번째행 [5,6,7,8] 세번째행 [4,3,2,1] 입니다. (바로 전 행이 존재해야하므로 2번째 행부터 시작해야합니다.)

 

시작행은 두번째 행입니다. 즉,현재행은 두번째 행입니다. [5,6,7,8]

현재행의 바로 전 행은 첫번째 행 입니다. [1,2,3,5]

 

바로 전 행에서 1번째 열의 제외한 숫자 [2,3,5] 중 가장 큰 숫자는 5입니다.

현재행의 1번째 열에 더해주면  5 + 5 이므로 10이 됩니다.

바로 전 행에서 2번째 열의 제외한 숫자[1,3,5] 중 가장 큰 숫자는 5입니다.

현재행의 2번째 열에 더해주면  6 + 5 이므로 11이 됩니다.

이와 같이 진행해주면 두번째 행은 [10,11,12,11]이 됩니다.

 

이렇게 4개 숫자가 다 바뀌었다면 다음 행으로 넘어갑니다. 그러면 현재행은 세번째행 [4,3,2,1]으로 바뀌고 바로 전 행은 두번째 행이므로 [10,11,12,11]이 됩니다.

아까와 같은 방식으로 바로 전 행에서 1번째 열의 제외한 숫자 [11,12,11]에서 가장 큰 숫자는 12입니다.

현재행의 1번째 열에 더해주면 4 + 12 이므로 16이 됩니다.

이와 같이 진행해주면 [16,15,13,13]이 됩니다.

 

이렇게 진행하다가 마지막행이 되었을 경우엔 마지막행의 가장 큰 숫자를 반환해주면 됩니다.

문제의 경우 3번째 행이 마지막 행이기 때문에 [16,15,13,13] 중 가장 큰 숫자는 16이므로 이것이 정답이 됩니다.

 

코드로 설명

land[1]부터 시작해야하기 때문에 land[0]을 변수 maxs에 담아놓습니다. => var maxs = land[0]

for문을 이용해 1부터 land의 배열크기만큼 반복해줍니다. for i in 1..<land.count{ ... }
현재행을 의미하는 land[i]를 current라는 상수에 넣어줍니다... = >  let current = land[i]

maxs값을 기억할 copyMaxs라는 변수를 만들어줍니다. (maxs의 값이 계속 변하기 때문에 만들어줘야 합니다.)=>  var copyMaxs = maxs 

for문 안에 또 for문을 사용하여 열의 갯수인 0부터 3까지 총 4번 반복해줍니다. for j in 0..<4{ ... }

 

해당 행의 최대값이 어떤 열인지 알아내기 위한 row라는 함수를 만들어줍니다.

func row(_ land:[Int]) -> Int {

    var max = 0

    for i in 0..<4 {

        if land[i] == land.max(){

            max = i

            break

        }

    }

    return max

}

 

 만약 해당 열이 최대값의 열이 아니라면 maxs의 열에 현재행의 열과 maxs의 최댓값을 더해줍니다. => if j != row(copyMaxs) {

                maxs[j] = current[j] + copyMaxs.max()!}

아니라면 maxs의 열에 현재행의 열과 maxs의 두번째로 큰 값을 더해줍니다. (copyMaxs를 큰 값으로 정렬한 뒤 copyMaxs[1]을 하면 두번째로 큰 값을 알아낼 수 있음) else { copyMaxs.sort(by:>)

                maxs[j] = current[j] + copyMaxs[1] }

그리곤 maxs의 가장 큰 값을 반환해줍니다. => return maxs.max()!

 

전체코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

import Foundation   func solution(_ land:[[Int]]) -> Int{     var maxs = land[0]     for i in 1..<land.count{         let current = land[i]         var copyMaxs = maxs         for j in 0..<4{             if j != row(copyMaxs) {                 maxs[j] = current[j] + copyMaxs.max()!             }else{                 copyMaxs.sort(by:>)                 maxs[j] = current[j] + copyMaxs[1]             }         }     }     return maxs.max()! }   func row(_ land:[Int]) -> Int {     var max = 0     for i in 0..<4 {         if land[i] == land.max(){             max = i             break         }     }     return max } Colored by Color Scripter