[#2812] 크게 만들기

문제

#2812 크게 만들기
Gold3
적용 알고리즘: Greedy 알고리즘

---

풀이 방법

• 첫 자리 수와 나머지 자리의 수를 별도로 계산한 뒤, 결과에서 합친다.
• k개를 제거한다면, 숫자의 맨 앞자리에서 k개 중 가장 큰 수가 해당 수의 첫 번째 수가 된다.

코드 흐름

1. 첫째 자리 수를 구한다.
2. 나머지 수에 대해서, 가장 큰 수를 구하고, 해당 수 왼쪽의 수들 중에서 해당 수보다 작은 수를 가장 작은 수부터 제거한다. 총 k개(만약 첫째 자리에서 n개가 제거되었다면 k - n가 됨)가 제거되거나, 문자열 끝에 도달했다면 루프를 빠져나온다.
3. 남아있는 k가 있다면, 이는 숫자가 내림차순으로 다 정렬된 상태이므로 숫자의 맨 끝에서 k개를 추가로 제거해준다.

코드

import time

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

start = time.time()

# 인덱스 0~k까지의 숫자를 배열에 저장
can = [num[i] for i in range(k + 1)]

idx = can.index(max(can))       # 가장 큰 수의 인덱스 탐색
k -= idx
first = max(can)

num = num[idx:]     # 원본 숫자에서 앞부분 떼어내기

can = [num[i] for i in range(1, len(num))]
nn = 0

while(len(can)):
    cnt = 0
    for i in can:
        if (i != ""):
            cnt += 1

    if (k == 0 or nn == cnt):
        break

    temp = sorted(can, reverse=True)

    max_num = temp[nn]
    for j in range(can.index(max_num, nn)):
        sub_str = sorted(can[0:can.index(max_num, nn)])

        if (sub_str[j] < max_num and k > 0 and sub_str[j] != ""):
            n_idx = can.index(sub_str[j])
            can[n_idx] = ""
            k -= 1
    nn += 1

if (k > 0):
    can = can[0:len(can) - k]

string = ""
for i in can:
    string += i
print(first + string)

end = time.time()
print(end - start)

체감 난이도: 4.8/5
왜 내 알고리즘에는 결함이 없는 것 같은데 자꾸 시간초과가 뜬다… 다른 테스트 케이스에 대해 무한루프가 걸려서 그런 것인지는 모르겠다.