프로그래머스 연습문제 Lv. 1 <과일장수> python, 문제 해석 및 풀이

 

처음으로 스터디원들과 함께하는 공통 문제를 풀어보았다~

난이도는 가볍게 Lv 1!

 

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

프로그래머스

---

문제에 대한 간단한 이해

값어치가 다른 과일을 상자로 묶어 최저가로 판매하는 문제입니다.

입출력에 대한 이해

과일의 최댓값 k, 상자안의 사과 갯수 m, 그리고 사과값이 들어있는 리스트가 주어지고 이를 통해 최대 판매 가격을 도출합니다.

문제에 대한 세부 이해

1. 주어진 것(입력값)

과일의 최댓값 k, 상자안의 사과 갯수 m, 그리고 사과값이 들어있는 리스트는 값의 높낮이와는 별개로 무작위로 주어집니다.

 

2. 구하고자 하는 것(출력값)

과일값의 최대값을 구해야 합니다.

 

3. 규칙

리스트 안의 값들이 무작위로 주어지므로 리스트 안의 값들을 정렬할 필요가 있습니다.

 

- 가장 단순한 첫 방법은 sorted를 사용하여 리스트 안을 정렬 후 큰 숫자들부터 처리하는 방법입니다. 정렬 알고리즘은 일반적으로 시간 복잡도를 O(nlogn)을 가지고 있습니다. 아래 두 번째 블로그에서 알 수 있듯 파이썬에서 리스트 정렬은 O(nlogn)입니다.

참고:

https://yabmoons.tistory.com/250

[ 정렬 ] 정렬별 장단점 및 시간복잡도

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

 

- 두 번째 방법은 사과의 값이 1부터 9까지로 굉장히 작은 숫자로 제한되어 있으므로 갯수만 세는 방법입니다. 리스트를 한번 돌면서 각 값에 해당하는 개수를 사과 갯수가 들어갈 새로운 리스트에 저장해줍니다. 이렇게 하면 O(n)시간 안에 답을 구할 수 있습니다.

 

두 번째 방법이 시간이 더 적게 걸리므로 두 번째 방법을 이용하여 풀어보겠습니다.

 

- 어떤 방법으로든 사과 값들에 해당하는 정렬을 마치면 큰 숫자부터 사과 상자에 묶어서 넣어주고 남은 값들은 한 단계 작은 값으로 취급하여 보냅니다.

구현

- 개수가 들어갈 리스트를 구현해줍니다. 1~9까지 아홉개의 칸만 있으면 모든 사과 값들을 커버 가능하므로 처음부터 9개 짜리를 만들어도 괜찮지만 사과 값의 최댓값인 k가 주어졌으므로 크기가 k인 리스트를 만듭니다.

 

- score리스트를 한 번씩 돌면서 각 값에 해당하는 개수 값들을 1씩 증가시킵니다.

 

- 이제 큰 숫자부터 돌면서 묶음으로 넣어주고, 남은 사과들은 그 다음으로 큰 갯수로 추가시켜줍니다.

def solution(k, m, score):
    answer = 0
    ### k값의 범위가 작으므로 score문 한 번만 돌기 위해 리스트에 개수로 저장

    # score값은 1부터 k까지 가능 -> 0부터 k-1까지 인덱스 필요
    k_list = []
    for i in range(k):
        k_list.append(0)

    # score값들을 한 번 돌면서 각 인덱스에 개수를 저장
    for s in score:
        k_list[s-1] = k_list[s-1] + 1

    # 큰 숫자부터 돌면서 큰 값들로 이루어진 사과를 상자 안에 넣기(큰 값들만 먼저 모아야 최대가 되므로)
    for i in range(k-1, -1, -1):
        # (i+1)*m의 값을 가지는 사과 박스 개수 (실제 사과 가격은 i+1임)

        i_box = k_list[i] // m

        # 합산
        answer += (i_box * m * (i+1))

        # 남은 사과 박스 개수
        if i != 0:
            # 마지막 남은 사과들이 아닐 땐 다음 인덱스로 넘김
            k_list[i-1] = k_list[i-1] + (k_list[i] % m)

    return answer

---