백준 온라인 저지, 그리디 / 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

힌트

W3sicHJvYmxlbV9pZCI6IjI4MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWFjOGMgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVjNzkwXHViOWFjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjMjJiXHVjNzkwIEtcdWFjMWNcdWI5N2MgXHVjOWMwXHVjNmNjXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEsgJmx0OyBOICZsZTsgNTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzkwXHViOWFjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgMFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjJiXHVjNzkwXHVjNWQwXHVjMTFjIEtcdWFjMWNcdWI5N2MgXHVjOWMwXHVjNmUwXHVjNzQ0IFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgxMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktFS1MiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGFuZCBTbGF2a28gYXJlIGJvcmVkIGF0IG1hdGggY2xhc3MgYWdhaW4gc28gdGhleSBjYW1lIHVwIHdpdGggbmV3IGdhbWUuIE1pcmtvIHdyaXRlcyBkb3duIGFuIE4gZGlnaXQgbnVtYmVyLCBhbmQgU2xhdmtvJnJzcXVvO3MgdGFzayBpcyB0byBvYnRhaW4gdGhlIGxhcmdlc3QgcG9zc2libGUgbnVtYmVyIGFmdGVyIGhhdmluZyByZW1vdmVkIGV4YWN0bHkgSyBkaWdpdHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgaGltIGRvIHRoYXQhJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOIGFuZCBLICgxICZsZTsgSyAmbHQ7IE4gJmxlOyA1MDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIE4gZGlnaXQgbnVtYmVyLiBUaGlzIG51bWJlciBzdGFydHMgd2l0aCBub24temVybyBkaWdpdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGxhcmdlc3QgcG9zc2libGUgbnVtYmVyIFNsYXZrbyBjYW4gb2J0YWluIGJ5IHJlbW92aW5nIEsgZGlnaXRzIGZyb20gdGhlIGdpdmVuIG51bWJlci4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 가장 자리수가 높은 숫자는 가장 숫자가 커야하기 때문에 앞에 숫자부터 하나씩 탐색하며 앞에 숫자가 뒤에 나오는 숫자보다 작을 경우 이를 빼준다.
- 한번 빼줄때마다 해당 위치에서부터 차례대로 다시 탐색을 진행한다.
- 만약 전부 탐색을 진행했음에도 더이상 뺄 숫자가 없다면 제일 뒤에 있는 숫자를 빼야하는 남은 숫자만큼 뺀다.

코드

# https://www.acmicpc.net/problem/2812
# 접근방법
# 가장 자리수가 높은 숫자는 가장 숫자가 커야하기 때문에 앞에 숫자부터 하나씩 탐색하며 앞에 숫자가 뒤에 나오는 숫자보다 작을 경우 이를 빼준다.
# 한번 빼줄때마다 해당 위치에서부터 차례대로 다시 탐색을 진행한다.
# 만약 전부 탐색을 진행했음에도 더이상 뺄 숫자가 없다면 제일 뒤에 있는 숫자를 빼야하는 남은 숫자만큼 뺀다.
n, k = map(int, input().split())
number = [x for x in input()]

array = [int(number[0])]

i = 1
while i < len(number):
    while len(array) > 0 and int(number[i]) > array[-1]:
        if k == 0:
            break
        array.pop()
        k -= 1 
    array.append(int(number[i]))
    # print('number[i]: ', number[i])
    # print('array: ', array)
    i += 1

while k > 0:
    array.pop()
    k -= 1

for x in array:
    print(x, end = '')