[BOJ / Python] 2812 - 크게 만들기 / 그리디 / 문제 데이터 추가 기여

2812번: 크게 만들기

풀이

주어지는 N, K가 최대 500,000이기 때문에 

수를 받아서, 앞의 숫자가 뒤에 나온 숫자보다 작을 경우 쳐내는 방식으로 풀었다.

4 2

1924

1 -> 9를 받으면 1이 없어지고

2 -> 4를 받으면 2가 없어지는 방식이다.

 

9421과 같이 뒤의 두 숫자를 삭제해야 하는 경우에도 정상적으로 동작하도록 print하는 인덱스 슬라이싱을 [:n-k]로 정해 둔다. 

 

코드

 

n, k = map(int,input().split())
num = list(input())
result, dk = [], k
# 앞에 나온 숫자가 뒤에 나온 숫자보다 작을 경우 쳐낸다는 마인드
for i in range(n):
    while dk>0 and result:
        if result[-1] < num[i]:
            result.pop()
            dk-=1
        else:
            break
    result.append(num[i])
# k가 0 이상인데 남은 수가 같은 수일 경우를 생각해 줘야 한다
print(''.join(result[:n-k]))

 

잘못된 풀이 ( 다른 테스트 케이스를 넣어 봤는데 결과가 잘못 나옴 )

n, k = map(int, input().split())
num = list(input())
result = []
for i in range(n):
    while k > 0 and result:
        if result[-1] < num[i]:
            result.pop()
            k -= 1
        else:
            break
    result.append(num[i])
print(''.join(result[:n-k]))

처음 제출했던 코드고 통과되었지만, 제출하고 다시 생각해 보는 과정에 이상함을 느낀 코드다.

 

위의 풀이와의 차이는 변수 dk의 유무이다. k값을 가져와 초기화하는 dk 변수 없이 k로 연산을 수행하면,

그리디로 숫자를 뺄 때에 k의 수가 줄어들게 되어 정상적인 값을 출력하지 못한다.

위의 코드는

7 5

9929191을 받을 경우 2와 1이 삭제된 99991에서 k=3 (2와 1을 빼면서 값이 2 감소함)으로 연산하게 되어, 

99991[:7-3=4] => 9999를 출력하게 된다. 

하지만 답은 99이다.

현재 데이터 수정 요청을 한 상태이니 받아들여진다면 내 BOJ 첫 기여가 된다.

잘못된 위 풀이의 반례
7 5
9929191

5 3
99291

6 3
773671

+)

문제가 재채점되고 데이터를 추가한 사람으로 기록되었다. 소소하지만 기분 좋다.ㅎㅎ

데이터 추가한 사람