프로그래머스: 과일 장수

[level 1] 과일 장수 - 135808

문제 링크

성능 요약

메모리: 10.1 MB, 시간: 0.01 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2023년 12월 4일 3:23:10

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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

---

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #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합니다.

풀이

###############################################################################
24개의 테스트 중 16번 테스트 케이스만 실패(해당 코드를 쓰는데 기억이 안나서 다시 작성하다 정답 맞춤)
###############################################################################
def solution(k, m, score):
    answer = 0
    score.sort()
    bag = []
    cnt = 0
    while True:        
        if cnt < m and len(score) > 0:
            bag.append(score.pop())
            cnt += 1

        elif len(bag) == m or len(score) == 0:
            if len(bag) >= m:
                answer += min(bag)*m
                bag = []
                cnt = 0
            else:
                return answer

    return answer

###############################################################################
                                    수정후
###############################################################################
def solution(k, m, score):
    answer = 0
    score.sort()
    bag = []
    cnt = 0
    while len(score) > 0:        
        if cnt < m:
            bag.append(score.pop())
            cnt += 1

        elif len(bag) == m:
            answer += min(bag)*m
            bag = []
            cnt = 0

    if len(bag) == m:
        answer += min(bag)*m

    return answer

느낀점

score리스트의 길이가 1 ~ 1,000,000 까지이기 때문에 while 또는 for loop을 한번만 사용할 수 있는 문제다. 최대한 정해진 시간 내에 풀기 위해서 리스트의 길이를 슬라이싱 하는것 보다 시간 복잡도가 O(1)인 pop()을 사용하게 됐다. 사실 문제에서 m의 크기가 10까지만 커질 수 있어서 가능했던것 같기도 하다. m이 score의 크기처럼 커지게 된다면 문제가 있었을텐데 다행이라 생각한다.

여튼, 풀이에서 보는것 처럼 처음 문제를 제출했을 때, 16번 테스트 케이스만 실패가 나오게 됐다. 사실 아직까지도 정확한 이유를 알지 못했다...(지금 이 블로그를 작성하는 중에 1번 코드를 다시 쓰다가 기억이 안나서 되짚어보며 작성하는데 정답을 맞춰버림 - 2번 풀이로 통과하기 전까지는 무슨 짓을 해도 16번 테스트 케이스를 통과 못했는데 2번을 통과하고 원래 코드를 수정하니 고쳐지는 아이러니;)

이 문제를 맞힌 시점부터, 오답을 알 수가 없음....

아래에 수정된 코드는 위와 비슷하지만 while이 끝나는 조건을 바꿨다. 1번 풀이 같은 경우에는 무한히 while을 순환하며 cnt의 값이 m보다 작을때까지 bag에 score에 있던 값을 넣고 아래에서 bag에 들어있는 과일의 값을 계산한다. 이후 이 과정이 계속 반복되는데 elif 안에서 len(score) == 0을 추가해서 while이 끝나는 조건을 추가했다.

2번 같은 경우에는 1번과 유사하지만 while이 끝나는 조건을 score가 비어있을 경우라고 설정했다. 이후 cnt가 m보다 작을때까지 bag에 과일을 추가하고 가방에 든 과일의 개수가 m과 같아지면 값을 계산했다. 이 과정이 score가 empty가 될 때 까지 지속하고 마지막에 가방에 담긴 과일의 개수가 m과 같은지 다른지 확인하고 결과를 출력한다.

풀이가 약간 두서가 없지만, 해당 문제를 풀면서 느낀것은 수많은 케이스들 중에 어느 하나를 실패하면 그것을 찾는데 상당히 오래걸릴뿐 아니라 찾기도 쉽지 않은것 같다. 앞으로도 계속 공부하면서 이런 것들을 꾸준히 생각하고 적용해야 될 것 같다.