[알고리즘] 프로그래머스 - 큰 수 만들기

grefer·2021년 10월 31일
0

알고리즘

목록 보기
1/5

문제설명

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

처음에 생각한 해결법

레벨 2 문제임에도 불구하고 처음부터 아이디어가 전혀 안 떠올랐다. 분명히 큰 자릿수의 작운 숫자를 최 우선으로 삭제하는 것이 방법이긴 했는데, 이걸 어떻게 표현해낼 방법이 없었다.

왜?

"그리디"라는 단어에 너무 매몰되다 보니까, 항상 그때의 최선의 선택을 한다 는게 말로는 알겠지만 어떻게 해결해야 할지 전혀 몰랐다. 아직 그리디에 대해서 공부가 부족한건 아닌가 싶다.

해결법

  1. 숫자 배열을 한 자리씩 탐색하면서 스택에 담는다.
  2. 이 때, 현재 자리의 숫자 > 스택 top에 담긴 숫자 라면 현재 자리의 숫자 <= 스택 top이 될 때 까지 스택을 pop한다.
  3. 스택 pop 횟수가 k회가 되면 탐색을 중단한다. 이 때, 모든 숫자를 탐색하지 않았다면 남은 숫자를 stack에 모두 담는다.
  4. pop 횟수가 k회가 되지 않았는데 모든 숫자를 탐색했다면 k회 pop 할때 까지 스택을 pop한다.
def solution(number, k):
    answer = []
    idx = 0
    num = k
    
    for index, digit in enumerate(number):

        while answer != [] and answer[-1] < digit and num > 0:
            answer.pop()
            num -= 1
            
        answer.append(digit)
        
        if num <= 0:
            idx = index
            break
            
    if num > 0:
        while num > 0:
            answer.pop()
            num -= 1
            
    if idx != 0:
        answer.append(number[idx+1:])
    
            
    return ''.join(answer)

TIL

  • 난 아직 멀었다. 열심히 그리고 꾸준히 하자.
profile
개발자가 되고싶다 열심히하자

0개의 댓글