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 를 써서 틀리기도 했다...)
나름 발전한 점은, 이제 문제를 보고 아 어떤 유형을 묻는 문제이구나를 먼저 파악하려고 한다는 점이고,
부족한 점은, 문제를 너무 착하게 보고 있다는 점. 문제를 변형시키지 말란 말이 없는데 왜 그렇게 문제를 감싸니 현수야..
또 부족한 점 발견! 다른 사람들은 파이썬을 잘 알고, 파이썬의 내장 기능들을 잘 활용하고 있었다. 예를 들어 몇 개씩 건너뛰면서 반복하는 거라든지.. 그래서 파이썬 자체에 대한 공부도 조금은 필요하지 않나 하는 생각이 들었다.
그래도 오늘 알고리즘 하나 풀어서 뿌듯함!
'알고리즘' 카테고리의 다른 글
[BOJ / 12933 / Python] 오리 (1) | 2023.09.22 |
---|---|
[BOJ / 1913 / Python] 달팽이 (0) | 2023.09.20 |
[BOJ / 2578 / Python] 빙고 (0) | 2023.09.20 |
[BOJ / 20546 / Python] 기적의 매매법 (0) | 2023.09.19 |
바킹독 알고리즘 0x07강 덱 요약본 (1) | 2023.01.31 |
댓글