프로그래머스 LV2. 큰 수 만들기 - 그리디

 

 

 

프로그래머스 LV2. 큰 수 만들기 문제입니다. 짧고 심플해서 만만해보이지만 생각 외로 어렵더라구요. 분명 예전에 쉽게 풀었을만한 문제인데 스택을 떠올리기까지 많은 박치기를 했습니다.

 

 

그러다가 숫자의 순서가 뒤바뀌지 않고 최댓값을 찾는 점에서 뭔가 스택 느낌이 나는 걸 파악하고 풀었습니다. 이거 뭐더라, 그 스택 () 매칭 문제랑 비슷한 거 같아요.

 

스택 응용 : 괄호 검사 문제

 

 

일단 순서가 유지된다는 점에서 앞에서부터 스택에 넣고, 크기 비교를 통해 스택의 마지막 숫자와 현재 숫자의 비교를 통해 최댓값을 찾는 알고리즘을 사용할 겁니다.

 

일단 for문을 통해 전체 문자열을 순회할겁니다.

    그리고 내부 while 문을 통해 스택의 맨 위와 현재 문자를 비교하고, 만약 스택 맨 위가 더 작다면 꺼낼 껍니다.

        while문을 돌면서 값을 비교합니다. 이 때 스택에 있는게 더 작다면 꺼낸 이후 다시 업뎃을 해줘야겠죠?

        그래서 while 문 내에는 pop과 k값을 줄여주는 로직

    while 이 끝나면 push 를 해주면서 전체 문자열을 순회하면 끝날 겁니다.

 

그러고 나서도 k가 남아있다면? k개를 지워줘야하니깐 stack의 끝에서부터 날릴 겁니다.

 

def solution(number, k):
    stack = []
    
    for num in number:
        while stack and k > 0 and stack[-1] < num:
            stack.pop()
            k -= 1
        stack.append(num)
    
    # 제거해야할 숫자가 남았다면 뒤에서부터 제거
    if k > 0:
        stack = stack[:-k]
        
    answer = ''.join(stack)
    
    return answer

 

로직을 이해하는 게 어렵지, 한 번이라도 자료구조나 알고리즘 공부해봤으면 코드는 엄청 간단히 짜집니다.

 

 

다른 분들 코드도 살펴봤는데, 저랑 동일하게 풀었더라구요.

 

스택을 사용한 대표적인 그리디 유형입니다!