2812 크게 만들기

아이디어

아이디어 1

카테고리 분류가 그리디랑 스택이길래, 순간 "맨 앞자리가 제일 큰 수를 선택 하면 되지 않을까?" 라는 생각을 해버림..

아이디어 2 (챗지피티 스포일러...)

챗지피티가 스포해버림.. 결국 지워가는 게 맞았다 (지운 횟수를 카운트하면서)
지운 횟수 = pop을 한 횟수

구현

제출 1 (아이디어 1으로 구현, 메모리 초과)

n, k = map(int, input().split())
target = input()
choose_count = n - k
answer = []

def choose(idx, iter_count):
    global target
    global choose_count
    global answer
    searching_range = target[idx + 1 : len(target) - (choose_count - iter_count)]
    # print(searching_range)
    chosen_num = max(searching_range)
    answer.append(chosen_num)
    if choose_count == iter_count:
        return
    idx_iter = searching_range.index(chosen_num) + idx + 1 
    return choose(idx_iter, iter_count + 1)

choose(-1, 1)

[print(ans, end="") for ans in answer]

앞에서부터 제일 큰 수를 골라서 추가하는 로직으로 가다 보니, 탐색할 범위를 슬라이싱해서 찾고 max 함수도 쓰고.. 난리가 났다.

‼️ 메모리 초과의 결정적 원인 - 재귀함수에서 슬라이싱 사용

슬라이싱은 대상의 특정 부분을 '복사'해서 새로 만들게 된다 -> 저장공간이 새로 필요함!!

(+ 재귀함수 호출 자체도 메모리를 먹는다 -> 함수 호출 스택)

제출 2 (제출 1 수정, 시간 초과)

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
number = input()
choose_count = n - k
chosed_count = 0
stack = []
idx = -1

while chosed_count < choose_count:
    for i in range(idx + 1, len(number) - choose_count + chosed_count + 1):
        if i == idx + 1:
            stack.append((i, number[i]))
        else:
            if number[i] > stack[-1][1]:
                stack.pop()
                stack.append((i, number[i]))
    idx = stack[-1][0]
    print(stack[-1][1], end="")
    chosed_count += 1

쌩고생하면서 재귀함수도 빼고 슬라이싱도 빼고 했더니만.. 이번엔 시간초과..

‼️ 시간 초과의 원인 - while문 안의 for 문 (이중 순회)

이제는 n에 가까운 범위를 이중탐색하는 방법은 웬만해선 안먹힌다고 봐야 한다..

이러고 나서.. GPT가 스포함..

제출 3 (아이디어 2로 구현, 정답..일 줄 알았으나 오답)

n, k = map(int, input().split())
number = input()

stack = []
erase_count = 0

for num in number:
    if erase_count == k:
        stack.append(int(num))
        # print(stack)
    else:
        if stack == []:
            stack.append(int(num))
            # print(stack)
        else:
            while True:
                if stack == [] or stack[-1] >= int(num) or erase_count == k:
                    break
                stack.pop()
                erase_count += 1
                # print(stack)
            stack.append(int(num))
            # print(stack)

[print(numb, end="") for numb in stack]

아이디어 그대로 구현해보니까 생각보다 테스트케이스에서 오답이 많이 나왔다.
특히 모든 과정에서 erase_count를 계속 확인하도록 하는 작업이 포인트였다.
(그래서 while문 안에 있는 조건문에 erase_count == k 조건이 달렸음)

그렇게 테스트케이스도 다 정답 나왔고 이제 제출하면 정답!! 인 줄 알았으나..

제출 4 (정답)

# 위 코드 마지막 print문 바로 위에
while erase_count < k:
    stack.pop()
    erase_count += 1

이걸 안넣어주면 연속된 숫자만 있는 경우 지우지를 않게 된다!!
그래서 맨 마지막에 erase_count가 k보다 작을 경우 안 지운 횟수만큼 stack에서 pop하는 과정을 추가.
드디어 정답.. 힘겹다..