Programmers / 큰 수 만들기 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 큰 수 만들기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

def solution(number, k):
    answer = ''

    front = list(number[:k])
    front_max = front.index(max(front))
    k -= front_max

    back = list(number[front_max:])

    for i in range(len(back)):
        if k == 0:
            answer = answer + ''.join(back[i:])
            break
        if i < len(back) - 1 and back[i] < back[i + 1]:
            k -= 1
        else:
            answer += back[i]

    return answer

 

문제를 봤을 때 가장 큰 수를 만드는 방법은 i번째 숫자가 있을 때 i + 1 번째 숫자랑 비교해서 i + 1번째 숫자가 더 크면 i번째 숫자를 삭제하면 된다는 방법이 떠올랐다.

 

하지만 위 코드는 테스트 결과에서는 통과했지만 코드 자체가 공간을 많이 잡아먹어서 그런가 통과를 하지 못했다.

 

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

 

stack에 숫자를 넣어서 다음 숫자가 나오면 stack에 있는 숫자랑 비교해서 스택에 있는 숫자가 더 작으면 pop()해서 삭제한다. 그렇게 큰 숫자들만 모아서 정리를 했다.

---

※ 알아야 할 것

 

주식가격 문제랑 비슷했다. 이와 같은 문제를 참고하면 좋을 것 같다.

프로그래머스