큰 수 만들기(프로그래머스) 문제풀이

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=python3

프로그래머스

 

 

문제 접근 방식

처음 문제를 접했을 때 완전탐색을 떠올렸으나 number의 자릿수가 1e6이므로 다른 방법을 찾으려 했다. 숫자를 순회하며 현재 수를 기준으로 어떻게 하면 될 것 같았지만 해결법을 찾지 못해 다른 분의 풀이를 참고했다. 풀이 방법의 핵심은 스택을 활용하는 것이다.

 

 스택에는 숫자를 저장하게 되며, [number의 현재 숫자]를 기준으로 스택의 top 값이 작다면 해당 top 값을 제거해주고 [현재 숫자] 를 stack에 넣어준다.

 

이렇게 스택 자료구조를 사용해서 풀 수 있다는 것은 알겠는데, 왜 하필 FILO 특징을 가진 stack 자료구조를 썼을까 의문이들었다. 단서를 찾아보자면..

1. 기존 숫자 배열의 순서는 유지해야하고 가장 큰 숫자가 앞쪽에 위치해야한다
>> 이를 위해서, 내림차순을 유지하는 리스트가 필요하다(제거하는 동안 내림차순 유지)

2. 만약 중간에 리스트의 특정 구간보다 큰 수가 나타나면 해당 숫자들을 제거해야한다
>> eg. 리스트=[6,5,3,2,1] , 현재 숫자 = 4
>> 3,2,1의 숫자를 제거해줘야한다. 즉, 뒷부분을 제거해줘야하기 때문에 stack 자료구조가 필요하다

 

이러한 이유 때문에 스택 구조를 활용해서 문제를 풀었어야 한다.

 

 

시간 복잡도

number를 for문으로 1번 순회해야하며, number의 최대 길이가 1e6이므로 시간내에 동작한다.

 

 

코드

from collections import deque
def solution(number, k):
    stack=deque()
    count=0
    for num in number:
        while count<k and stack and stack[-1]<num:
            stack.pop()
            count+=1
        stack.append(num)
    stack=list(stack)
    return ''.join(stack[:(len(number)-k)])

 

 

 

회고

110옮기기에 이어 두 번째 stack 활용 문제이다. 그때 stack을 사용하는 문제 풀이가 임팩트가 커서 stack을 의심하기는 했으나 이번 문제풀이와는 관련이 없다고 판단하고 다른 방법을 찾았는데 stack 문제였다. 문제는 단순해보이는데 자료구조를 잘 활용하지 못하면 꼬이기만해서 stack, queue 등의 자료구조를 활용하는 문제를 연습할 필요가 있다..