사용자 도구

사이트 도구


ps:problems:programmers:42883

큰 수 만들기

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42883
문제명큰 수 만들기
레벨Level 2
분류

스택

시간복잡도O(n)
인풋사이즈n<=1,000,000
사용한 언어Python
해결날짜2021/06/23
태그

고득점 Kit - 탐욕법

풀이

  • BOJ의 크게 만들기와 동일한 문제.
  • 차근차근 생각해보자. 가장 큰 수를 만들려면 맨 앞자리에 가능한 가장 큰 수를 배치해야 한다. 맨 앞자리에 올 수 있는 수는, 앞에서부터 k+1번째 까지의 수이다. 이중에서 가장 큰 수를 찾아서, 맨 앞자리에 배치한다. 가장 큰 수가 x번째에 있었다면, 이제 그 다음 자리에 올 수 있는 수는 x+1번째부터 k+2번째까지의 수이다. 이중에서 가장 큰 수를 찾아서, 두번째 자리에 배치하고.. 이런식으로 처리하면 된다.
  • 이 작업은 스택을 이용하면 쉽게 구현할수 있다. i-1번째 숫자까지 사용해서 만든 가장 큰 수가 스택에 저장되어 있을때, i번째 숫자가 현재 만들어진 수의 마지막자리 숫자보다 크다면, 마지막자리 숫자를 지운다. 그 앞자리 숫자도 i번째 숫자보다 작다면 그 숫자도 지운다. 이렇게 반복해서, i번째 숫자보다 작은 숫자들을 모두 지운 다음 (스택에서 pop하고), i번째 숫자를 뒤에 붙이고 (스택에 push), i+1번째 숫자로 넘어가면 된다. 이때 지운 숫자의 갯수가 k가 되면 더이상 지우지 않고 그냥 스택에 바로 붙이는 것을 반복하면 된다.
  • 이렇게 스택을 이용해서 구현했을때의 시간 복잡도는 O(n)이 된다

코드

"""Solution code for "Programmers 42883. 큰 수 만들기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42883
- Solution link: http://www.teferi.net/ps/problems/programmers/42883
"""


def solution(number, k):
    stack = []
    removed_count = 0
    for ch in number:
        while stack and removed_count < k and stack[-1] < ch:
            stack.pop()
            removed_count += 1
        stack.append(ch)
    return ''.join(stack[:len(number) - k])

토론

댓글을 입력하세요:
Q Y B E A
 
ps/problems/programmers/42883.txt · 마지막으로 수정됨: 2022/01/19 15:30 저자 teferi