[백준/Python] 2812번 : 크게 만들기

문제 분석

https://www.acmicpc.net/problem/2812

숫자 k개를 지워서 만들 수 있는 가장 큰 수를 구하는 문제이다.

풀이

가장 큰 수를 만들려면 최대한 큰 숫자가 앞에 위치하게 해야 한다.

예를 들어 4177252841에서 4개를 지워서 가장 큰 수를 만들면 4177252841 즉 775841이 된다.

원리를 생각해보면 앞에서부터 순회하면서 뒤에 더 큰 숫자가 있다면 해당 숫자를 지워서 더 큰 숫자가 앞에 위치하도록 하고 있다.

이때 스택을 활용하면 적절하게 구현 가능하다. 스택은 조건에 따라 불필요한 데이터를 제거하고 필요한 데이터를 유지할 때 적합하다.

이 문제에서 조건은 현재 값보다 다음 값이 크면 현재 값을 삭제하는 것이므로 구현 방법을 다음과 같이 떠올릴 수 있다.

n=7 k=4

7654321

처럼 앞에서부터 큰 수가 차례로 나올 때는 스택에 들어갈 수 있는지 판단하는 과정에서 k개만큼 숫자가 제거되지 않는다. 

따라서 마지막에 k>0일 때 (제거해야 할 숫자의 개수가 남았을 때)는 뒤에서부터 남은 숫자만큼 제거해주면 가장 큰 수를 얻을 수 있다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
string = sys.stdin.readline().strip()
numbers = list(map(int, string))
stk = [] # 우리가 구할 숫자가 저장되는 스택
for next in numbers:
    while k>0 and stk and next>stk[-1]: # 다음 숫자가 스택의 top보다 크면 스택에서 pop()하고 큰 수를 집어넣기
        stk.pop()
        k-=1
    stk.append(next)
if k>0: # k개 모두 지우지 못했을 때
    stk = stk[:-k]
for i in stk:
    print(i, end="")

오답노트

내가 처음 짤 때는 스택에 삭제할 숫자들(k개)을 저장했다.

그러나 조건에 맞는 데이터만 저장할 때 쓰이는 스택의 특성을 생각한다면 

스택에 삭제할 숫자들이 아니라 가장 큰 수가 될 수 있는지 아닌지를 판단해서 넣는 게 더 스택을 사용하는 목적에 맞는 게 아닐까 하는 생각이 들었다. 

 

나중에 다시 풀어봐야지 

 

틀린 코드 : 

import sys

n, k = map(int, sys.stdin.readline().split())
string = sys.stdin.readline().strip()
numbers = list(map(int, string)) # 앞에서부터 k개의 숫자를 잘라 리스트에 넣음
stk = [numbers[0]]
result = []
for i in range(1, n):
    # numbers에서 하나를 꺼내서 스택의 top과 비교
    num = numbers[i]
    top = stk[len(stk)-1]

    if num <= top: # top이 더 크거나 같으면 스택에서 pop해서 result에 추가 # 13번째 줄
        result.append(stk.pop())
    if len(stk)<k: # 스택에 최대 k개의 숫자만 버릴 수 있음
        stk.append(num)
    else: # 버릴 k개의 숫자가 모두 정해졌다면 나머지 숫자들은 그냥 result에 append
        for tmp in numbers[i:]:
            result.append(tmp)
        break

for i in result:
    print(i, end="")

1. 스택에 첫 번째 숫자를 미리 넣어두고 numbers에서 다음 숫자를 꺼내 스택의 top과 비교한다.

2. top이 더 크면 pop해서 result에 append하고 더 작은 다음 숫자를 스택에 넣는다.

3. 스택에 k개의 버릴 숫자들을 다 넣었다면 아직 검사하지 않은 남은 숫자들은 모두 result에 append

 

반례:

10 4
4177252841
output: 477584
answer: 775841