오늘 푼 문제
https://school.programmers.co.kr/learn/courses/30/lessons/135808
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
내 코드
파이썬으로는, 풀었던 코드가 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 개의 간격으로 인덱스를 생성하여, 상자를 구성할 수 있는 위치를 찾는 것.
느낀점
간단하게 풀 것이라고 생각했는데, 잘 되지 않아서 생각을 계속했다. 덕분에 이제 이 정도 난이도의 문제는 좀 더 자신감 있게 다가갈 수 있게 된 것 같다.
앞으로도 하나의 문제를 풀 때, 최대한 많은 고민과 생각을 해서 얻어가도록 하고, 마지막에 다른 사람의 코드를 보면서 새로운 것을 배우는 방식으로 공부해야겠다.