[Python] 백준 2812 골드3 크게 만들기

백준 2812 골드 3 크게 만들기

2812번: 크게 만들기

 

문제

---

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

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

 

출력

---

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

오답 기록

처음 생각했던 풀이는, 남겨둬야 하는 최소한의 수만 남기며 검사하여 최댓값을 뽑는 방법이다.

 

만약 6 자릿수를 만들어야 한다면 첫 수를 뽑을 때, 뒤에 최소 5자리 수는 남아야 하므로, n - 5 자리까지만 검사해 최댓값을 뽑는다. 이걸 6자리가 될 때까지 반복하는 방법으로 구현했다. 

n, k = map(int, input().split())
num = list(map(int, list(input())))

temp = 0 # 맨 앞자리 시작 인덱스
step = n - (n - k - 1) # 검사 범위
ans = [] # 정답 리스트
mx = 0 # 검사 범위 내의 최댓값

# 맨 앞자리 먼저 검사
for i in range(step): 
    if num[i] > mx:
        mx = num[i]
        temp = i

ans.append(mx)

# n-k 자리수가 될 때 까지 반복
while len(ans) != n - k:
    mx = 0
    step = n - (n - k - len(ans)) # 뽑힌 수 만큼 step범위를 줄여준다

    for j in range(temp + 1, step + 1): # 최근에 뽑힌 수의 인덱스 다음부터 검서
        if num[j] > mx:
            mx = num[j]
            temp = j 

    ans.append(mx)

print(''.join(map(str, ans)))

예제는 다 맞지만 시간초과가 나버린다.. 거의 완전 탐색으로 푼 수준이라 스택으로 값을 넣고 지우며 시간 복잡도를 줄여보는 방법을 찾아봤다. 직접 짜진 않았고 다른 블로그를 참고했다.

 

 

 

 

코드 내놔!  참고한 블로그 ↓ 

velog

 

정답 / 풀이

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

stack = []

for num in number:
    while stack and stack[-1] < num and k > 0:
        stack.pop()
        k -= 1
    stack.append(num)

if k > 0 :
    print(''.join(stack[:-k]))

else:
    print(''.join(stack))

위의 블로그를 참고해 작성한 코드다. 남의 코드를 굳이 가져온 이유는 그동안엔 int로 형변환해서 크기를 비교해 왔는데,  문자열 자체로 크기 비교할 생각을 안 해봤어서 기록할 겸 가져왔다.

 

풀이

number에 있는 숫자를 하나씩 stack에 넣고 그다음 숫자와 비교한다.

만약 다음 숫자가 stack에 있는 숫자보다 크면 stack.pop()을 해주면서 가장 큰 숫자를 앞 쪽에 위치하도록 한다.

stack 제일 위에 쌓인 수가(가장 나중에 들어온 숫자) 더 크거나 작으면 k가 0이 될 때까지 stack에 숫자를 쌓아준다.

이러면 123456이 들어오면 6만 남나?라는 생각이 잠시 들었지만, k 만큼만 지우므로 자연스럽게 n - k 개의 수가 남는다. 

k개까지만 지워야 하므로 k > 0 이상일 때만 수행하고, 만약 k개 미만으로 숫자를 지웠다면 뒤에 숫자가 k개만큼 남아있다는 뜻 이므로 남은 수를 지우고 출력한다.