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

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

2812번: 크게 만들기

 

import sys
input = sys.stdin.readline


# p 이전 숫자들 중에 -1이 아닌 것이 있다면 해당 인덱스를 받아옴
def getPreviousNumberIndex(p, numberList):
    p -= 1
    while p >= 0:
        if numberList[p] == -1:
            p -= 1
        else:
            return p

    return -1


def getRemovedMaxNumberList(numberList):
    kCount = 0
    p, n = 0, 1

    # 앞에서부터 숫자 비교하면서 삭제(= -1로 바꿈)
    while n <= N-1:
        if kCount >= K:
            return numberList

        if numberList[p] < numberList[n]:
            kCount += 1
            numberList[p] = -1

            previousNumberIndex = getPreviousNumberIndex(p, numberList)
            if previousNumberIndex != -1:
                p = previousNumberIndex
                continue

        p = n
        n += 1

    # 남은 것들이 있다면, 뒤에서 모두 처리(-1)
    for i in range(N-1, -1, -1):
        if kCount >= K:
            break

        if numberList[i] != -1:
            numberList[i] = -1
            kCount += 1

    return numberList


def solution(s):
    numberList = [int(c) for c in s]

    removedMaxNumberList = getRemovedMaxNumberList(numberList)
    for n in removedMaxNumberList:
        if n != -1:
            print(n, end="")


N, K = map(int, input().split())
s = str(input().rstrip())
solution(s)

 

getRemovedMaxNumberList()가 핵심이다. 우선 p, n은 비교 대상 둘의 인덱스다. 그리고 이후에 '삭제'의 의미는 해당 원소를 -1로 바꾸는 것을 뜻한다.

kCount를 증가시키면서 K와 같아질 때까지 원소들의 대소관계를 비교하면서 삭제해준다. 다만, 원소를 삭제했다면 p를 p 이전에 있는 -1이 아닌, 가장 가까운 숫자로 이동시킨다. 이 위치를 알기 위해 getPreviousNumberIndex()를 사용하는데, 만약 이 결과 값이 -1(p 이전의 모든 원소가 -1)일 경우는 걸러준다.

 

사진 한 장으로 요약하면 위와 같다. 빨간 밑줄은 각각 p, n을 뜻한다.

이렇게 비교 연산이 끝나고 kCount가 k까지 올라오면 바로 numberList를 리턴해준다.

 

하지만 kCount가 k를 만족하지 못하는 경우가 있다. 이 때는 단순히 뒤에 있는 숫자들을 계속해서 지워주면 된다.

 

이번 풀이는 다른 분들의 풀이와 비교하면, 심플하지 못하고 시간복잡도도 떨어진다. -1로 바꾸고, -1이 아닌 값까지 탐색을 하는 과정이 좋지 못하다. 데큐를 하나 만들고, 이 곳에 완성된 숫자들을 저장하는 용도로 바꾸면 훨씬 좋은 풀이가 만들어진다.