[그리디] 백준 2812번: 크게 만들기 / 골드 5

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

2812번: 크게 만들기

import sys
n, k = map(int, input().split())
lst = input()

target = n-k
answer = ""
pick = 0
i = 0
while pick < target:
    maxnum = -sys.maxsize
    maxidx = None

    find = False
    for j in range(i, pick + k + 1):
        if lst[j] == '9':
            answer +='9'
            pick +=1
            i = j +1
            find = True
            break
        if maxnum < int(lst[j]):
            maxnum = int(lst[j])
            maxidx = j

    if not find:
        answer += lst[maxidx]
        pick += 1
        i = maxidx + 1

    if target - pick == len(lst)-i:
        answer += lst[i:]
        break
print(answer)

접근 방법: 

target: n-k, 내가 선택해야하는 문자의 총 개수를 의미

pick : 현재까지 내가 선택한 문자 수

i : 인덱스

 

그러면 target - pick 은 내가 앞으로 선택해야 할 문자의 개수를 의미하게 된다.

만약 내가 앞으로 x개의 문자를 더 선택해야 한다면 현재 인덱스부터 끝에 x-1개를 제외한 지점까지 최댓값을 조사하면 된다. 끝에 있는 x-1개는 절대로 이번에 택할 수 없기 때문이다. 

여기서 인덱스 구하기가 좀 복잡하고 헷갈리는데,

끝에서부터 x-1번째에 해당하는 원소의 음수 인덱스는 (target - pick -1 )*(-1) = 1-target+pick이다.

양수 인덱스로 바꿔주려면 여기에 len(lst)를 더해주면 된다. 따라서 인덱스는

1-target+pick+len(lst) = 1-(n-k)+pick+n = pick + k + 1이 된다.

이것이 코드 14번째 줄에서 pick + k + 1을 해주는 이유다.

 

최댓값을 직접 조사하는 이유는 최적화 때문인데, 9를 찾으면 바로 그 9를 택하기 위해서다.

9를 찾게되면 for문을 중지시키고 인덱스도 9 다음의 인덱스를 할당받게 된다.

 

마지막에 if target - pick == len(lst)-i: 을 조사하는 이유도 최적화 때문인데(이거 안하면 시간초과 ..)

target - pick, 즉 내가 앞으로 택해야 할 문자 수와 현재 인덱스로부터 남은 lst 개수가 같다면 

더이상 erase 하지 못하고 전부 택해야 하기 때문이다.

 

 

- 배운점:

음수 인덱스를 양수 인덱스로 바꾸려면 +len을 해준다.

양수 인덱스를 음수 인덱스로 바꾸려면 -len을 해준다.