TIL_DAY_17 프로그래머스 - 과일 장수

오늘 푼 문제

https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

내 코드

 

파이썬으로는, 풀었던 코드가 Swift 에서는 풀리지 않았다. 파이썬 코드부터 뭔가 잘못되었던 것 같다..

아래는 내가 처음 풀었던 Swift 코드.

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    var answer: Int = 0
    var tmp: Int = 0    // 상자 안에 담기 사과의 개수
    
    let s = score.sorted(by: > )
    
    for i in s {
        if tmp < m {    // 상자에 사과를 더 넣을 수 있는 경우
            tmp += 1
        } else {
            // 가장 마지막에 넣은 사과의 점수는 p
            answer += i * m
            tmp = 0
        }
    }
    
    return answer
}

 

내림차순으로 정렬한 후 배열을 순회하면서 마지막에 넣은 사과의 점수가 p(상자에 담긴 사과 중 가장 낮은 점수) 라고 생각했다.

 

그러나, 단순히 마지막에 넣은 사과의 점수를 사용하는 방식은 상자마다 가장 낮은 점수가 아닌, 마지막에 추가된 사과의 점수만을 고려하는 것이기에 '가장 낮은 점수가 아닐 가능성'이 존재한다.

또한 내림차순으로 정렬한 후 단순히 순서대로 상자를 채워나가는 방식은, 상자를 구성하는 최적의 방법을 놓칠 수 있다. 예를 들어, 특정 점수의 사과를 고르게 분배하여 더 많은 상자를 판매하고 전체 이익을 극대화할 수 있는 경우가 있을 수 있다. 

 

 

상자를 채우는 동안 가장 낮은 점수를 기록하고, 상자가 가득 찼을 때 이를 이용해 가격을 계산.
그리고 상자가 가득 차면 다음 상자로 넘어가기 전에 초기화. 

하는 내 기존 로직을 그대로 사용하는 대신, 어떻게 하면 문제의 요구사항을 충족시킬 수 있을까를 고민하였다.

 

일단 해당 문제의 솔루션으로

각 상자를 채울 때 상자에 담긴 사과 중 가장 낮은 점수를 찾아, 그 점수를 기준으로 상자의 가격을 계산하는 것.

여기서 중요한 것은 상자를 채우는 과정에서 각 상자에 대해 최소 점수를 실시간으로 업데이트하는 방식을 사용하였다.

 

수정된 코드

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    var answer: Int = 0
    var tmp: Int = 0    // 상자 안에 담긴 사과의 개수
    var minScoreInBox: Int = k + 1 // 상자 안 최소 점수, 가능한 최대 점수보다 1 큰 값을 초기값으로 설정
    
    let sortedScores = score.sorted(by: >) // 내림차순으로 정렬한 사과 점수
    
    for i in sortedScores {
        tmp += 1 // 사과를 상자에 넣음
        minScoreInBox = min(minScoreInBox, i) // 상자에 담긴 사과 중 최소 점수 갱신
        
        if tmp == m {    // 상자가 가득 찼으면
            answer += minScoreInBox * m // 상자 가격을 계산하여 추가
            tmp = 0 // 상자를 초기화
            minScoreInBox = k + 1 // 최소 점수도 초기화
        }
    }
    
    return answer
}

 

var minScoreInBox: Int = k + 1 

이 부분에서 minScoreInBox를 가능한 최대 점수보다 1 큰 값으로 초기화하였다. 이는 상자에 담긴 사과 중 가장 낮은 점수를 찾기 위한 기준점으로, 실제 사과 점수보다 항상 높은 값으로 설정하여 어떤 사과 점수와 비교해도 최초에는 그 사과 점수가 최소값이 되도록 한 것.

 

let sortedScores = score.sorted(by: >)

이렇게 하는 이유는 높은 점수의 사과부터 상자에 넣으면서, 가능한 한 높은 점수의 사과로 상자를 채우기 위함이다. (그러나 최종적으로 상자의 가격은 상자에 담긴 사과 중 가장 낮은 점수에 의해 결정된다.)

반복문 내에서, 각 사과를 상자에 넣으면서 minScoreInBox를 업데이트하였다.

(min(minScoreInBox, i)를 사용하여 현재 상자에 담긴 사과 중 최소 점수를 지속적으로 갱신하는 과정)

그리고 상자가 가득 차면 해당 상자의 가격을 계산하여 answer에 더하고, 다음 상자를 위해 tmp와 minScoreInBox를 초기화하였다.

 

 

---

 

그리고 해당 문제를 푼 다른 사람의 Swift 코드를 보았다.

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    let s = score.sorted(by: >)
    return stride(from: m-1, to: score.count, by: m)
        .reduce(0) { $0 + s[$1] * m }
}

 

score 배열을 내림차순으로 정렬한 후, m 간격으로 인덱스를 건너뛰며 해당 인덱스에 위치한 사과의 점수(s[$1])를 이용하여 가격을 계산하는 방식.

 

stride(from:to:by:): m 개의 간격으로 인덱스를 생성하여, 상자를 구성할 수 있는 위치를 찾는 것.

 

 

느낀점

간단하게 풀 것이라고 생각했는데, 잘 되지 않아서 생각을 계속했다. 덕분에 이제 이 정도 난이도의 문제는 좀 더 자신감 있게 다가갈 수 있게 된 것 같다.

 

앞으로도 하나의 문제를 풀 때, 최대한 많은 고민과 생각을 해서 얻어가도록 하고, 마지막에 다른 사람의 코드를 보면서 새로운 것을 배우는 방식으로 공부해야겠다.