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

- 문제 : https://www.acmicpc.net/problem/2812

 

- 정답 풀이 : 

예제3을 이해하자면 

 

k=4, result = [4,1]

(while) k=3, result = [4,7], k=2 result=[7]

k=2 result = [7,7]

k=2 result = [7,7,2]

k=1 result = [7,7,5]

k=1 result = [7,7,5,2]

k=0 result = [7,7,5,8]

k=0 result = [7,7,5,8,4,1]

 

25일 만에 그리디 50문제 2차 풀이 끝!!

N,K=map(int,input().split())
data=list(input())
result=[]
k=K

for i in range(N):

    #뺄 수 있는 횟수가 남아있고, 더 큰 숫자가 오른쪽에 있고, 아직 가장 큰 숫자가 오지 않았을 때
    while k>0 and result and result[-1]<data[i]:
    
        #result의 오른쪽 원소를 제거해야하므로
        result.pop()
        k-=1
        
    result.append(data[i])
    
print(''.join(result[:N-K]))

 

의아한건, 어차피 k==0이 될 때까지 루프를 돌리는데 마지막 result의 길이는 N-K인데 굳이 result[:N-K]로 설정해야하는 이유가 있나? 

하고 없이 돌려봤는데 75%에서 틀렸다. 어떤 경우 때문에 그런지 궁금하다,,,

 

해결

이 블로그를 참고하면 될 것 같다. 반례로 5 3, 43344가 있다. 이때 result=[4,4,4]가 나오는데 이때는 두자리 수만 출력해야하므로 44가 나오게 하려면 result[:N-K]를 해줘야한다