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

[문제]

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

주어진 숫자에서 순서는 유지한 채, k개의 수를 제거해 큰 수를 만들어내는 문제입니다. 즉 숫자들을 재조합하는 문제가 아니라는 것입니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

프로그래머스의 해당 문제와 동일한 문제입니다. 

 

숫자를 순서대로 순회 및 스택에 저장해, 스택의 숫자를 순간마다 가장 큰 수로 유지하면 해결 가능한 문제입니다.

 

출력 방식에 따라 소요 시간이 약 10배 정도 차이가 날 수 있습니다.

---

[초기화]

    def __init__(self):
        self.n, self.k = map(int, input().split())
        self.num = input()
        self.stack = []

---

[풀이]

    def solve(self):
        for i in range(self.n):
            while self.k and self.stack and self.stack[-1] < self.num[i]:  # 문자열이라도 단일 숫자는 순서로 크기를 비교
                self.stack.pop()
                self.k -= 1

            self.stack.append(self.num[i])

        print("".join(self.stack) if self.k == 0 else "".join(self.stack[:-self.k]))
        # 무조건적으로 k개 만큼 수를 제거해야 하므로 k가 남아있다면 처리해줘야 함
        # 위 로직으로 처리하면 완전하진 않지만 숫자가 내림차순의 형태거나 모든 숫자들이 동일하면 값을 제거할 수 없음
        # 5 3 11111
        # 6 4 765462

풀이 순서는 다음과 같습니다.

1. 숫자를 순서대로 스택에 저장합니다.
   • 스택에 저장된 값은 정답을 이룹니다.
2. 숫자를 저장하기 전, 모든 숫자를 제거하지 않았으며 스택에 가장 최근에 저장된 값이 현재 값보다 작은 값이라면 제거합니다.
   • 이때 숫자를 제거했으므로 k값을 감소시킵니다.
   • 반복문을 사용하는 이유는 값이 제거 됐을 때 남아있는 값이 현재 값보다 큰 값인지 확인하기 위함입니다.
   • 예제 입력 3의 경우 반복문이 아닌 단순 조건문으로 처리하는 경우 다음과 같아집니다.
   • 4 - 1 - 7 순으로 들어왔을 때 가장 큰 값을 만들기 위해선 당장 7을 남겨둬야 하지만 조건문으로 처리할 경우, 4 - 7이 스택에 남고 다음 숫자를 검사하게 됩니다.
   • 위와 같은 상황을 방지하기 위해 반복문을 사용합니다.
   • 예시
     4
     4 1
     4 7 제거 - 1
     4 7 7
     4 7 7 2
     4 7 7 5
     4 7 7 8 제거 - 5
     4 7 7 8 4
     4 7 7 8 4 1
3. 이후 k가 남아있는 경우를 고려해야 합니다.
   • 기본적으로 숫자 제거가 이뤄지는 상황에선 스택은 내림차순의 값을 유지하게 됩니다.
   • 하지만 숫자가 모두 동일하거나 내림차순의 형태로 구성되어 있으면 값의 제거가 이루어지지 않습니다.
   • k가 남아있을 때 스택의 값은 순차적으로 지금까지 만들 수 있는 가장 큰 수 + 아직 제거되지 않은 숫자로 구성되어 있으므로 남은 k개만큼 뒤에서 제거합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n, self.k = map(int, input().split())
        self.num = input()
        self.stack = []

    def solve(self):
        for i in range(self.n):
            while self.k and self.stack and self.stack[-1] < self.num[i]:  # 문자열이라도 단일 숫자는 순서로 크기를 비교
                self.stack.pop()
                self.k -= 1

            self.stack.append(self.num[i])

        print("".join(self.stack) if self.k == 0 else "".join(self.stack[:-self.k]))
        # 무조건적으로 k개 만큼 수를 제거해야 하므로 k가 남아있다면 처리해줘야 함
        # 위 로직으로 처리하면 완전하진 않지만 숫자가 내림차순의 형태거나 모든 숫자들이 동일하면 값을 제거할 수 없음
        # 5 3 11111
        # 6 4 765462


problem = Main()
problem.solve()

입력 값을 문자열로 처리하면 빠르게 처리할 수 있습니다.

class Main:
    def __init__(self):
        self.n, self.k = map(int, input().split())
        self.num = [int(i) for i in input()]
        self.stack = []

    def solve(self):
        for i in range(self.n):
            while self.k and self.stack and self.stack[-1] < self.num[i]:
                self.stack.pop()
                self.k -= 1

            self.stack.append(self.num[i])

        if self.k:
            self.stack = self.stack[:-self.k]

        answer = int("".join(str(i) for i in self.stack))
        print(answer)


problem = Main()
problem.solve()

위 코드처럼 정답을 만들 때, 값을 하나씩 가져와서 하나의 문자열 형태로 만드는 것을 많은 시간이 소모됩니다.

그렇기 때문에 출력형식을 정수형으로 지정한 것이 아니라면 문자열로 처리하는 것이 빠릅니다.

 

해당 코드를 마지막 정답 코드로 수정한 계기는 생각 이상으로 많은 시간이 소요되었기 때문입니다. 나아가 코드를 좀 더 줄여보고자 하였습니다.

 

불필요한 처리는 피할 수 있으면 최대한 피해야 한다는 것을 경험하였습니다.

---