(알고리즘) 과일장수

2024. 5. 18. 11:09TIL

신나는 주말!

주말에는 간단한 알고리즘 문제를 풀어보자!

 

🔥알고리즘 문제

 

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

  • 한 상자에 사과를 m개씩 담아 포장합니다.
  • 상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

  • (최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한사항

    • 3 ≤ k ≤ 9
    • 3 ≤ m ≤ 10
    • 7 ≤ score의 길이 ≤ 1,000,000
      • 1 ≤ score[i] ≤ k
    • 이익이 발생하지 않는 경우에는 0을 return 해주세요

입출력 예

k m score result
3 4 [1,2,3,1,2,3,1] 8
4 3 [4,1,2,2,4,4,4,4,1,2,4,2] 33

입출력 예  #2 설명

  • 다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

사과 상자가격

[1, 1, 2] 1 x 3 = 3
[2, 2, 2] 2 x 3 = 6
[4, 4, 4] 4 x 3 = 12
[4, 4, 4] 4 x 3 = 12

따라서 (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33을 return합니다.

 

내가 작성한 코드 

class Solution {
    fun solution(k: Int, m: Int, score: IntArray): Int {
    var answer: Int = 0
    var scoreList=score.toMutableList()
    scoreList.sortDescending()

    while (scoreList.size >= m) {
        val sublist = scoreList.subList(0, m)
        val leastNum = sublist[m - 1]
        answer += (leastNum * m)
        sublist.clear()
    }

    return answer
}
}

 

기능 구현에는 문제가 없지만 테스트11,12,13에서 시간초과로 인한 실패가 발생함

즉 작동은 하지만 너무 오래걸린다는것이 문제이다

 

내가 작성한 코드 해석

scoreList.sortDescending() :일단 score의 배열을 입력받으면 score을 내림차순으로 정렬을 진행

scoreList.subList(0,m)으로 0번째 값부터 m미만, 즉 m-1까지의 값을 sublist 변수에 저장함

sublist[m-1] 로 담겨진 값중 가장 작은 값인 마지막 값, 즉 m-1번째 값을 leastNum이라는 변수에 저장함

answer+= leastNum*m : return값인answer에 leastNum을 더하고

sublist.clear()로 sublist 안의 값을 삭제해서 새로운 값을 받을수 있도록 함

 

개선한 코드

class Solution {
    fun solution(k: Int, m: Int, score: IntArray): Int {
    var answer: Int = 0
    score.sortDescending()

    for (i in m-1 until score.size step m) {
        answer += score[i] * m
    }

    return answer
}

}

 

개선한 코드 해석

기존 코드와 마찬가지로 score.sortDescending()으로 큰값부터 정렬되도록 함

for(i in m-1 until score.size step m) 반복문을 사용함으로서 i가 1씩 증가하는것이 아닌 m만큼 증가하도록 설계 -> 이는 곧 n번부터 n+3까지 반복을 하고 각각의 값을 저장한다음에 마지막 값을 leastNum에 저장하는것이 아닌 한번에 내가 원하는 값에만 접근해서 반복하기때문에 가독성 뿐만아니라 프로그램 실행속도에도 영향을 미치게 됨


 

 

 

 

더 개선해야할 Point

for문은 무조건 1씩증가하면서 반복된다고만 생각하였는데  step 키워드를 사용해서 내가 원하는 만큼 증가하도록 설계할 수 있다는 점을 알게되어 이 점을 적극활용하면 좋을 듯하다.

 

 알고리즘 GitHub :https://github.com/kotlin2024/algorithm/commit/862d71e4a1ae8b01b713c38893114af9ae7cf9a1

 

'TIL' 카테고리의 다른 글

JPA  (0) 2024.05.20
(SQL) 식품 종류별 비싼 식품 정보 조회하기  (0) 2024.05.19
간단한 API를 직접 만들어보자 (3)  (0) 2024.05.17
간단한 API를 직접 만들어보자(2)  (0) 2024.05.16
간단한 API를 직접 만들어보자(1)  (0) 2024.05.15