[프로그래머스] 큰 수 만들기 - Python

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

프로그래머스

아이디어

• 그냥 number문자열에서 k만큼 반복문으로 가장 작은 수를 제거하면 되는거 아닌가?

구현(틀림)

def solution(number, k):
    answer = ''
    number = list(number)
    for i in range(k):
        number.pop(number.index(min(number)))
        
    return "".join(number)

하나 실패

틀린 원인 분석1

• 아이디어 자체에 오류가 있었다.
• 작은수만 제거하는 것이 아니라 맨 앞자리의 수가 가장 크게 만들면 된다.
• for문을 돌며 현재가 다음 요소보다 작으면 그 요소를 삭제하게 만들자
• 마지막 수가 제일 작다면 그 수를 삭제하자

구현(시간초과)

def solution(number, k):
    answer = ''
    number = list(number)
    for _ in range(k):
        for i in range(len(number)):
            if i == len(number)-1:
                number.pop()
                break
            if number[i] < number[i+1]:
                number.pop(i)
                break
    return "".join(number)

흠 시간초과 2개

틀린 원인 분석 2

• 2중for문을 허용하지 않는듯
• 그냥 스택을 이용해 큰 자리의 수부터 result 스택에 넣는다
• 넣는 수가 맨 위의 수 보다 크면 result 에서 하나 pop
• pop하는 개수가 k와 같아지면 나머지는 다 넣어주고 result 출력

구현(정답)

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        
    return ''.join(answer[:len(answer) - k])

맞았당

 

마무리

• 스택을 사용해야하는게 핵심인 것 같다.
• 그냥 FOR문을 통해 검토하는건 2중으로 돌아야해서 이 방법으로는 풀 수 없었음..