[baekjoon] 백준 2812번(파이썬): 크게 만들기

문제

2812번: 크게 만들기

- N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 문제이다.

- N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

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

알고리즘

- 자릿수와 제거할 횟수를 입력받는다.

- 숫자를 입력받아 리스트 변수에 넣는다.

- 스택을 사용할 리스트를 만든다.

- 첫 번째 반복문을 통해 숫자의 자릿수를 확인한다.

- 두 번째 반복문은 입력받은 숫자보다 작은 수가 스택 리스트에 없을 때까지 반복한다. 즉, 입력받은 숫자보다 작은 스택 리스트를 끝에 순서대로 모두 제거한다.

- 스택 리스트의 마지막 수와 입력받은 숫자를 비교하여 스택 리스트의 마지막 수가 작으면 그 수를 팝하고 숫자 제거 횟수를 -1 해준다.

- 스택 리스트의 마지막수가 크다면 두 번째 반복문을 멈춘다.

- 두 번째 반복문이 끝나면 다음 스택에 현재 비교했던 수를 추가한다.

- 총자릿수에서 제거할 횟수를 뺀 만큼 반복하여 숫자를 출력한다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().strip()))
stack = []

# 숫자 제거 횟수 체크
del_num = k

# 반복문을 통해 n자리까지 확인
for i in range(n):
    # 제거할 수가 있고 리스트가 있으면 반복한다.
    # i번째 수보다 작은 리스트의 끝 수를 모두 제거하기 위해서
    while del_num > 0 and stack:

        # 리스트의 끝 수와 i번째 수를 비교
        if stack[len(stack) - 1] < num[i]:

            # 리스트의 끝 수가 작으면 팝하고 숫자 제거 횟수를 -1 해준다.
            stack.pop()
            del_num -= 1

        # 리스트의 끝 수가 더 크면 멈춰준다.
        else:
            break

    # 리스트에 i번째 수를 추가한다.
    stack.append(num[i])


# 리스트에 담겨있는 수를 자릿수에서 제거할 횟수를 뺀 만큼 순서대로 출력한다.
result = ""
for i in range(n - k):
    result += str(stack[i])
print(result)

결과

위 코드에서 첫 번째 반복문 맨 밑에 print(stack)을 작성하게 되면 스택에 어떤 형태로 숫자가 추가되고 제거되는지 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 처음에 del_nom이 0 보다는 크지만 스택에 아무것도 없기 때문에 반복문에 들어가지 않고 바로 스택에 i번째 수를 추가해 1이 들어간 것을 확인할 수 있다. 그다음 숫자인 9는 del_nom이 0 보다 크고 스택에 원소가 있기 때문에 다음 반복문에 들어가게 된다. 반복문에 들어가서 스택의 끝 수인 1과 9를 비교해 9가 더 큰 것을 확인하고 스택의 끝 수를 팝하여 없앤다. 숫자 1을 제거를 했기 때문에 숫자 제거 횟수를 -1 해주고 스택에 아무것도 없으므로 반복문을 빠져나와 스택에 i번째 수를 추가해 9가 들어간 것을 확인할 수 있다. 그다음 숫자인 2도 위와 같은 방법으로 반복문에 들어가지는데 2는 스택의 끝 수인 9보다 작기 때문에 반복문을 멈춰주고 스택에 i번째 수를 추가해 9와 2가 스택에 들어가 있는 것을 확인할 수 있다. 4도 마찬가지로 위와 똑같은 방법으로 들어가지는데 4는 스택의 끝 수인 2보다 크기 때문에 스택의 끝수를 팝하고 제거 횟수를 -1 해준다. 그리고 스택에 i번째 수를 추가해 9와 4가 스택에 들어가 있는 것을 확인할 수 있다. 모든 자릿수를 확인했기 때문에 반복문에 나오게 되고 스택에 담겨있는 수를 자릿수에서 제거한 횟수만큼 반복하여 순서대로 출력하면 된다.

<출력화면>

위 다른 예시에 출력 화면을 보도록 해보자. 처음에 4는 위에 예시와 똑같은 이유로 스택에 들어간 것을 확인할 수 있다. 그다음 숫자인 3은 스택의 끝 수인 4보다 작기 때문에 반복문을 멈추고 스택에 추가된다. 그다음 수인 3도 똑같은 이유로 스택에 추가되어 스택에 4, 3, 3이 되어 있는 것을 확인 할 수 있다. 여기서부터 코드를 잘 봐야한다. 그 다음 숫자인 4는 스택의 끝 수인 3보다 크기 때문에 스택의 끝 수인 3을 팝하고 제거 횟수를 -1 해주게 된다. 그리고 반복문이 끝나는게 아니라 제거횟수가 0보다 크고 스택에 원소가 아직 있기 때문에 또 반복이 된다. 이때 스택에 마지막 수가 3으로 다시 바뀌게 되고 그 다음 숫자인 4와 또 비교하게 된다. 그 다음 숫자인 4가 스택에 마지막 수인 3보다 또 크기 때문에 스택의 끝 수인 3을 또 팝하고 제거 횟수를 -1 하게 된다. 여기서 또 제거횟수가 0보다 크고 스택에 원소가 아직 있기 때문에 반복문이 끝나지 않고 반복하게된다. 그 다음 스택의 끝 수인 4와 그다음 숫자인 4를 비교하게 되고 두 수가 같기 때문에 이 반복문은 끝이 나고 스택에 i번째 숫자인 4를 추가하여 스택에 4, 4가 되어 있는 것을 확인할 수 있다. 여기서 말하고자 하는 것은 i번째 수보다 작은 리스트의 끝 수를 모두 제거한다는 것이다. 그리고 마지막으로 4와 비교하게 되는데 위 이유와 똑같이 스택에 추가가 된다. 따라서 스택에는 4, 4, 4가 들어가게 된다. 하지만 우리가 원하는 것은 5자리 수중에 3개의 수를 뺀 두 자릿수이다. 그래서 마지막에 n -k만큼 반복하여 우리가 원하는 자릿수 까지만 순서대로 출력하여 결과 값을 받는 것이다.

github

junjange/CodingTest