광물 캐기

업데이트 사항

수정 : 2024-07-05 [시간 복잡도 추가]

 

코딩테스트 연습 - 광물 캐기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 코드

# 2024-07-05
def make_pick_dict(picks):
    answer={}
    for i in range(len(picks)):
        if i==0:
            key_name='diamond'
        elif i==1:
            key_name='iron'
        else:
            key_name='stone'

        answer[key_name]=picks[i]
    return answer

# 피로도 계산하는 함수
def pirodo_cl(now_pick, now_mir_list):
    answer = 0
    for i in now_mir_list:
        if now_pick=='diamond':
            answer+=1
        elif now_pick=='iron':
            if i=='diamond':
                answer+=5
            else:
                answer+=1
        else:
            if i=='diamond':
                answer+=25
            elif i=='iron':
                answer+=5
            else:
                answer+=1
    return answer

def solution(picks, minerals):
    answer = 0
    pick_dict = make_pick_dict(picks)
    
    seq_mineral = []
    for i in range(0,len(minerals), 5):
        seq_mineral.append(minerals[i:i+5])
    # 곡괭이가 부족할수도 있으니 캘수있는것만
    seq_mineral = seq_mineral[:sum(picks)]
    # 다이아, 돌, 아이언 많은 순으로 정렬
    seq_mineral = sorted(seq_mineral, key=lambda x:(x.count('diamond'), x.count('iron'), x.count('stone')), reverse=True)
    # 정렬된 리스트를 순회하며 피로도 계산
    for now_mir_list in seq_mineral:
        if pick_dict['diamond']>0:
            now_pick = 'diamond'
        elif pick_dict['iron']>0:
            now_pick = 'iron'
        else:
            now_pick = 'stone'
        
        pick_dict[now_pick]-=1

        answer+=pirodo_cl(now_pick, now_mir_list)
    
    return answer

 

 

시간 복잡도

1. 사전 만들기 : 크기가 3으로 고정 (상수시간)
2. seq_mineral 리스트 만들기 : minerals 리스트를 순회하며 만드므로 (선형시간)
3. seq_mineral 자르기 : sum(picks) 만큼 자르므로 (선형시간)
4. seq_mineral 정렬 : 정렬이므로 (선형로그시간)
5. 피로도 계산 : seq_mineral 리스트 순회하며 계산하므로 (선형시간)

 

최악의 경우 시간복잡도는 : 선형로그시간 ( O(nlogn) )