[프로그래머스] 큰 수 만들기 - 그리디 greedy | 스택 Stack (python) (2)

5. 두번째 풀이 

스택을 이용하여 풀이가 가능하다. for문을 이용하여 스택에 숫자들을 넣으며 다음 조건들을 만족시켜주면 된다.

 

1. 숫자를 넣었을 때 직전에 넣은 숫자가 더 작은 경우 자리를 바꾼다.
2. 가장 위에 있는 숫자를 pop한다.
3. 매 단계마다 1-2를 반복한다.
4. 빼낸 숫자가 k와 같아지면 num의 나머지 숫자들을 stack에 추가해주고 끝낸다.

def solution(number, k):
    num = list(number)
    stack = [num[0]]
    count = 0

    for i in range(1, len(num)):
        if count == k:
            stack = stack + num[i:]
            break

        stack.append(num[i])
        if stack[-1] > stack[-2]:
            while(len(stack) != 1 and stack[-1] > stack[-2] and count < k):
                stack[-2], stack[-1] = stack[-1], stack[-2]
                stack.pop()
                count += 1
    return "".join(stack[:len(num)-k])

 

문제를 푸는데 필요한 알고리즘을 공부하고 코드를 짜니까 훨씬 수월했지만 중요한 것은 코딩이 아니라 효율적인 알고리즘 자체를 빠르게 생각해내야 한다는 것이다. 단순히 문제만을 푸는게 중요한게 아니기 때문에 시간복잡도에 대해 더 생각해보고 공부할 필요를 느꼈다. 

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42883

 

코딩테스트 연습 - 큰 수 만들기