[백준 2812] 크게 만들기

크게 만들기(2812)

문제 출처 : https://www.acmicpc.net/problem/2812

N자리의 숫자에서 K개의 숫자를 지워 가장 큰 숫자를 만드는 문제 입니다.

문제 이해하기

문제를 잘 생각 해보면 뒤의 숫자가 앞의 숫자보다 크다면 앞의 숫자를 지워주면서 가장 큰 숫자를 찾아나가야 합니다.

숫자를 한 자리씩 탐색 시작
현재 숫자가 앞의 숫자보다 크고, 지워야할 숫자가 남아 있다면 앞의 숫자를 제거

스택을 이용해서 숫자를 만들어 나가면 된다는 것을 느꼈다면 반은 성공한 것입니다.

예제 만들어 보기

예제에 있는 1924를 예를 들어보겠습니다. 1924에서 2개의 숫자를 빼서 가장 큰 숫자를 만들어야 합니다.

1924 탐색 시작
첫번째 숫자 1 탐색.
- 만든 숫자 : 1, K : 2
9 탐색. 1보다 크고, K가 남아 있기 때문에 1을 삭제.
- 만든 숫자 : 9, K : 1
2 탐색. 9보다 작기 때문에 숫자를 이어줌
- 만든 숫자 : 92, K : 1
4 탐색. 2보다 크고, K가 남아 있기 때문에 2를 삭제
- 만든 숫자 : 94, K : 0

위와 같이 예제 1924로 숫자를 찾았습니다. 만약 15924 였다면 처음의 1, 5를 제거해서 92가 가장 큰 숫자가 될 것 입니다. 즉 앞의 한 자리만 체크하는 것이 아니라 K가 남아 있다면 계속해서 앞의 숫자를 제거해나가야 합니다.

위의 로직만 있으면 좋겠지만 한 가지 규칙을 더 생각해야 합니다.

모든 숫자를 탐색했는데 K가 남아있다면 K개 만큼 뒤의 숫자를 제거

예를 들어 98765 라는 숫자가 있고 K값이 3이라면 모든 숫자를 탐색해도 숫자는 그대로 98765 입니다. K값이 전혀 사용 되지 않았다는 것을 알 수 있습니다. 이렇게 K값이 남게되면 뒤에 있는 3자리를 제거해서 98만 남기는 것입니다.

코드 작성하기

그럼 위에서 알게된 로직을 직접 구현해 보겠습니다.

입력 받기

N, k = map(int, input().split())
arr = input()

주어진 숫자의 길이 N과, 제거해야 할 숫자 k를 입력 받습니다. 다음으로 주어진 숫자를 arr에 넣습니다. input을 다른 문제들 처럼 map을 사용해서 숫자로 바꿔주는 것이 아니라 문자열 그대로 사용합니다. 숫자는 아무리 길어도 하나의 숫자입니다. 하지만 문자열은 하나 하나 따로 탐색이 가능 합니다.

스택 구현하기

ans = []
for a in arr:
    i = int(a)
    while ans and ans[-1] < i and 0 < k:
        ans.pop()
        k -= 1
    ans.append(i)

ans라는 리스트에 정답을 넣을 것입니다. arr의 원소를 하나하나 확인해 나가며 앞의 숫자와 비교해서 그냥 이어주던가, k값이 남아 있다면 앞의 숫자를 제거해 나가며 숫자를 만들어 나갑니다. 이 때 while을 사용하는 이유는 앞의 숫자가 작고, k가 남아있다면 계속해서 제거를 해나가기 위해서 입니다.

남은 k 지우고 결과 출력하기

if k:
    ans = ans[ :-k]
    
print(*ans, sep="")

k가 남아있다면 ans에서 k개 만큼 뒷 자리를 삭제합니다. 그리고 최종적으로 ans를 출력해 줍니다. ans를 출력할 때 리스트에 *을 넣어주면 Unpacking 되어 괄호가 사라집니다. 하지만 아직 쉼표( , ) 가 있어 이 부분도 변경이 필요합니다. 리스트를 출력하면 기본적으로 빈 칸 한 칸으로( “ “) 구분 됩니다. separate의 약자인 sep로 이 값을 변경할 수 있습니다. 기본적으로 sep 을 입력하지 않으면 빈 칸 한 칸이 출력됩니다. 이 sep 값을 붙어있는 값(””)으로 변경하면 더 우리가 원하던 값을 얻게 됩니다. 아래 리스트를 출력하는 방법을 보면서 위 코드를 이해하시기 바랍니다.

rst = [1, 2, 3, 4, 5]
print(rst)          # [1, 2, 3, 4, 5]
print(*rst)         # 1 2 3 4 5
print(*rst, sep='') # 12345

이 코드를 보면 알 수 있듯이 rst를 그대로 출력하면 리스트 그대로 출력됩니다. 여기에 *을 붙여 대괄호와 쉼표가 사라졌습니다. 마지막으로 separate 값을 제거해서 12345가 붙어서 출력된 것입니다.

전체 코드

전체 코드를 알아보겠습니다.

N, k = map(int, input().split())
arr = input()

ans = []
for a in arr:
    i = int(a)
    while ans and ans[-1] < i and 0 < k:
        ans.pop()
        k -= 1
    ans.append(i)

if k:
    ans = ans[ :-k]

print(*ans, sep="")

다빈치코딩