[프로그래머스] -그리디. 가장큰수

안녕하세요!

저는 드디어 그리디로 넘어왔습니당

 

그리디 문제는 처음에 갈피를 잡지 못하면 산으로 가게되는? 것 같습니다 ...

 

그래서 저는 한 세시간을 태우다가 돌아돌아 정답을 내었지요 ..

 

문제

풀이

처음에 생각했던 풀이는 dfs 였습니다.

그런데 시간초과 오류가 발생했고 .. 다른 풀이를 생각해내어야했습니다 !

 

그래서 생각해낸 것은 

 

"앞자리에 큰 숫자가 오는 것이 전체 수를 크게 만든다"

 

였습니다.

 

이에 stack을 활용하였습니당 !

stack을 사용한 이유는 담겨진 숫자의 제일 마지막 수와 새로 들어올 수의 크기를 비교하는 연산이 필요한데,

이 때 pop() 을 사용하는 것이 효율적이라고 생각했기 때문입니다.

 

stack을 활용해서 이 문제를 푼다면 다음과 같이 풀이가 가능합니다.

 

• number = "4177252841", k=4일 경우,
  • (k=4) []
  • (k=4) [4]
  • (k=4) [4, 1]
  • (k=3) [4]
  • (k=2) []
  • (k=2) [7]
  • (k=2) [7, 7]
  • (k=2) [7, 7, 2]
  • (k=1) [7, 7]
  • (k=1) [7, 7, 5]
  • (k=1) [7, 7, 5, 2]
  • (k=0) [7, 7, 5]
  • (k=0) [7, 7, 5, 8]
  • (k=0) [7, 7, 5, 8, 4]
  • (k=0) [7, 7, 5, 8, 4, 1]
  • retrun "775841"

나의 코드

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
        
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)