[개념] 그리디 + [프로그래머스] 큰 수 만들기

그리디 알고리즘은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"을 의미한다.

그리디는 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형

그냥 머리로 풀어야됨 방법 X

 

예제 1) 거스름돈

Q. N원을 거슬러 줄 때 최소 동전 개수로 거슬러 줘야한다. 동전 종류는 500,100,50,10 무한개

A. 가장 큰 화폐 단위부터 거슬러 주면 최소 개수 동전으로 거슬러줄 수 있음

 

test case ① 

N=1260

 

step1) 500원짜리로 거슬러 줄 수 있는 돈 => 500*2개 (1000원)

step2) 100원짜리로 거슬러 줄 수 있는 돈 => 100*2개 (200원)

step3) 50원짜리로 거슬러 줄 수 있는 돈 => 50*1개 (50원)

step4) 10원짜리로 거슬러 줄 수 있는 돈 => 10*1개 (10원)

 

 

 

프로그래머스 LV2 큰 수 만들기

문제

 

핵심 아이디어 💡

➀ 순서를 유지하면서 작은 숫자를 stack에서 빼낸다.

그러려면 총 빼야하는 개수 k보다 더 많이 빼지않도록 조건 걸고@@ 현재 숫자보다 작은 stack안의 숫자를 모두 빼내기

**무조건 앞자리숫자가 커야 좋은거니까 뒤에 더 작은 숫자가 있는지 고려할 필요 X, 지금 stack[-1]의 숫자가 가장 크기만 하면됨

def solution(number,k):
    answer=""
    
    stack=[number[0]]
    number=number[1:]
    for num in number:
        while stack and k>0 and stack[-1] < num:
                stack.pop()
                k-=1
        stack.append(num) #현재 숫자 push
        
    if k>0:
        stack=stack[:len(stack)-k]
    answer="".join(stack)
    return answer