[프로그래머스 / Python] 과일 장수

import numpy as np

def solution(k, m, score):
    answer = 0
    # m 이 주어진 배열의 길이보다 작을 때
    if m < len(score):
        mArray = []
        # 숫자 자체를 1씩 줄여나가기
        for j in range (k, -1, -1):
            # 주어진 배열 다 돌면서 반복
            for i in range (len(score)):
                # m 배열이 아직 다 안 채워졌음 > 넣으면 됨. 
                if len(mArray) < m :
                    if score[i] == j :
                        mArray.append(score[i])                        
                # m 배열이 다 채워졌음 > 결과에 더해주고, 비우고, 새로 넣으면 됨
                elif len(mArray) == m :
                    answer += min(mArray) * m
                    mArray = []
                    if score [i] == j :
                        mArray.append(score[i])
    # m 이 배열의 길이와 동일할 때 
    elif m == len(score):
        answer = min(score) * m
    # m 이 배열의 길이보다 클 때
    return answer

score = [1, 2, 3, 1, 2, 3, 1]
solution(3, 4, score)

 

내가 푼 풀이는, 문제의 조건을 바꿀 생각을 전혀 하지 않았다. 딱 보고 아 이거 그리디네~ 그럼 큰 것들부터 뽑아서 정리해야지 라고 생각만 했지, score 를 변형해서 내림차순 정렬한다는 생각을 전혀 하지 못했다.. 바본가..... 그래서 무진장 더럽게 풀었다. 

간단한 아이디어만 설명해보면, 

1. 전체 배열을 순회하는데, 그 중에서 제일 큰 수부터 골라 하나씩 줄여나간다. 

2. m 인 배열이 만들어지기 전까지는 계속 mArray 배열에 큰 수를 하나씩 넣다가

3. m 인 배열이 만들어지는 순간, 그 배열에 있는 것을 가지고 결과에 반영을 하고, 해당 배열은 다시 초기화 시켜버린다. 

 

이 정도였다. 나는 나름대로 이거 메모리 사용도 얼마 안 되고 괜찮은 코든데? 라고 생각했는데 시간 복잡도가 O(n^2)이나 되어버리는데다가 곳곳에 여러 실수하기 좋은 구간들이 많다. (elif 를 써야 하는데 그냥 if 를 써서 틀리기도 했다...)

 

나름 발전한 점은, 이제 문제를 보고 아 어떤 유형을 묻는 문제이구나를 먼저 파악하려고 한다는 점이고, 

부족한 점은, 문제를 너무 착하게 보고 있다는 점. 문제를 변형시키지 말란 말이 없는데 왜 그렇게 문제를 감싸니 현수야.. 

또 부족한 점 발견! 다른 사람들은 파이썬을 잘 알고, 파이썬의 내장 기능들을 잘 활용하고 있었다. 예를 들어 몇 개씩 건너뛰면서 반복하는 거라든지.. 그래서 파이썬 자체에 대한 공부도 조금은 필요하지 않나 하는 생각이 들었다. 

 

그래도 오늘 알고리즘 하나 풀어서 뿌듯함!