[백준 2812번] 크게 만들기 (Python)

> 파이썬, 자료 구조, 그리디 알고리즘, 스택

 

 

 

 

 

📖 문제 : 크게 만들기 (Python)

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

 

 

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

 

예제 입력 1 

4 2
1924

예제 출력 1 

94

 

 

 

 

 

내 코드

N, K = map(int, input().split())
num = list(map(int, input()))
stack = [num[0]]

for i in range(1, len(num)):

    while len(stack) > 0 and K > 0:
        if stack[-1] < num[i]:
            stack.pop()
            K -= 1
        else:
            break
    stack.append(num[i])

if K > 0:
    print(''.join(map(str, stack[:-K])))
else:
    print(''.join(map(str, stack)))

 

 

Point ! ⭐️ 

• 이 문제는 스택을 사용해야한다. 
  입력 값으로 주어진 수를 앞에서부터 읽어가며 스택에 넣는다. 
  이때 스택에 넣는 조건이 있는데,
  
  1) 이미 들어가 있는 수는 들어갈 수보다 커야한다.
  2) 들어갈 수가 이미 들어가있는 수보다 크면 들어가있는 수를 뺀다.
  3) 하나씩 빼면서 들어갈 수보다 큰 수가 나올 때까지 뺀다.
  4) 들어가 있는 수가 크도록 조건이 완성 되었다면 수를 넣어준다.
  
  근데 이 과정이 입력값을 보면, 수를 뺄 수 있는 횟수가 주어져있기 때문에
  그 횟수가 0이 될 때까지 빼는 것이다.
  
  또 여기서 생각해야될 것이 이미 뺄 수 있는 횟수가 0이 되어 다 써버렸는데
  들어가야할 수가 이미 들어가 있는 수보다 크다면 ?
  그냥 그 남은 수들은 크기 비교 상관 없이 다 넣어줘야 한다. 

 

 

예시를 들어가며 설명해 보겠다 !

5 3
48931

일단 맨 처음 수 4는 무조건 스택에 넣어준다. 

 

 

1) stack = [4], 들어갈 수 8 

=> 4 < 8 이므로 4를 빼준다. / K = 3-1 =2

2) stack = [8] 

3) stack = [8], 들어갈 수 9
=> 8 < 9 이므로 8을 빼준다. / K = 1

4) stack = [9]

5) stack = [9], 들어갈 수 3

=> 9 > 3 이므로 3을 그대로 넣어준다.

6) stack = [9, 3] 결국 스택에 이미 들어가 있는 수는 들어갈 수보다 더 커야한다. 

7) stack = [9, 3], 들어갈 수 1
=> 3 > 1 이므로 1을 그대로 넣어준다. 

8) 이렇게 완성된 stack = [9, 3, 1] 인데 아직 K = 1 이다.
여기서 1만큼 더 수를 없애야 하는데 없애는 방법은 가장 뒤에 있는 수를 남아있는 K만큼 빼주면 되는 것이다. 

그래서 정답은 stack = [9, 3] 으로 93이 되는 것 !

 

 

 

 

 

 

 

백준

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

2812번: 크게 만들기