BOJ / python3 백준 2812번 : 크게 만들기

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

2812번: 크게 만들기

문제

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

입력

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

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

출력

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

예제 입력 1 

4 2
1924

예제 출력 1 

94

예제 입력 2 

7 3
1231234

예제 출력 2 

3234

예제 입력 3 

10 4
4177252841

예제 출력 3 

775841

 

SOLUTION

1. 숫자 n이랑 k가 주어진다.

숫자 n에서 k개의 숫자를 지워서 가장 큰 숫자를 만들어야함. 

k가 지울 수 있는 횟수 이므로 숫자 하나를 제거할때마다 k - 1 을 해줘야함.

 

2. 입력받은 숫자 number을 숫자 하나씩 for문으로 검사하면서 

숫자를 입력받아서 answer배열에 추가하고, 

answer 배열에 값이 있고, cnt = k (지울 수 있는 횟수) 가 0보다 크고, answer 배열의 마지막 값이 num보다 작을 때 

answer 의 마지막 값을 삭제 해주고, 삭제를 진행 했으니 cnt -= 1

 

3. answer배열을 join을 이용하여 출력.

 

4. 입력 예시를 통해 자세하게 살펴보면 

n = 4, k = 2 

number = 1924

 

for문 과정

 1. num = 1  while문 조건 만족x(answer 배열에 아무것도 없음) , answer = [1] , cnt = 2

2. num = 9 while문 조건 만족, answer = [9]  , cnt = 1

3. num = 2 while문 조건 만족x (answer[-1] = 9 > 2) , answer = [9, 2] , cnt = 1

4. num = 4 while문 조건 만족, answer = [9, 4] , cnt = 0

 

for문 종료. cnt = 0, answer = [9, 4]

 

소스코드

import sys

n, k = map(int, sys.stdin.readline().split())
number = list(sys.stdin.readline())

answer = []
cnt = k

for num in number:
    while answer and cnt>0 and answer[-1] < num:
        del answer[-1]
        cnt -= 1
    answer.append(num)

print(''.join(answer[:n-k]))