99클럽 코테 스터디 20일차 TIL (큰 수 만들기 - 프로그래머스)

오늘의 학습 키워드:  Greedy, stack

문제: 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

풀이

1. 슬라이싱을 이용한 풀이 (시간 초과)

반복문과 슬라이싱을 이용해서 남겨두어야 하는 최소 자리의 수들을 제외하고 가장 큰 수의 값과 인덱스를 이용하는 방법이다. 그러나 number 자체가 커지면 확인해야 하는 수의 크기도 커지게 되어 시간 초과가 발생한다.

def solution(number, k):
    answer = ''
    number = [int(i) for i in number]
     return_len = len(number) - k
    
     while return_len:
         m = 0
         idx = 0
         for i in range(0,len(number)-return_len+1):
             if number[i] > m:
                 m = number[i]
                 idx = i
             if number[i] == 9:
                 break
         number = number[idx+1:]
         return_len-=1
         answer+=str(m)
  	return answer

 

2. stack을 이용한 풀이 (정답)

stack을 이용해서 수를 담아놓고 만약 제거가 가능한 개수가 남아있다면

스택에 들어올 다음 수보다 작은 값들을 모두 팝해주는 방법으로 진행하였다.

스택 연산의 시간복잡도는 상수 이므로 최악의 경우에도 O(n)으로 연산을 수행 가능하다.

def solution(number, k):
    answer = ''
    number = [int(i) for i in number]
    stack = []
    for i in number:
        if len(stack) == 0:
            stack.append(i)
        else:
            if stack[-1] < i and k > 0:
                while True:
                    if stack and stack[-1] < i and k>0:
                        stack.pop()
                        k-=1
                    else:
                        stack.append(i)
                        break   
            else:
                stack.append(i)
    
    stack = [str(i) for i in stack]
    stack = stack[:-k] if k > 0 else stack
    return ''.join(stack)

회고

stack과 queue를 적절하게 이용하는 방법을 찾아야할듯합니다. 그리디 문제를 만나면 사고가 제한되는 기분이라 이를 해결해야겠습니다.