Algorithm

백준 1467번: 수 지우기 (python)

by VICENTE97P4

Dec. 23, 2021, 2:24 p.m.

문제 링크: 1467번: 수 지우기 (acmicpc.net)

제가 풀었던 문제 중 정답 수도 적고, 구글링 했을 때 자료도 적었던 문제를 하나 해설해보겠습니다.

사실 구글링하면 하나 나오긴 하는데, 저는 잘 이해가 안 되어서.. 하나 올려보겠습니다.

입력으로는 원래 숫자를 주고, 그 다음 줄에는 지울 숫자를 주는 군요..

이거 푼다고 며칠을 머리를 싸맸는지 모릅니다.

엄청 다양한 방법을 시도해봤고 많이 틀렸습니다.

일단 지워야 하는 숫자 개수는 정해져 있으므로, 어떻게 지우든 남은 숫자의 길이는 같습니다.

그럼 결국 제일 큰 수가 앞에 와야 하는 거죠.

먼저 숫자를 지워나가는 쪽으로 생각해봤습니다.

1. 뒷자리에 있는 수가 앞자리에 있는 수보다 크면 지웁니다.

ex) 386512에서 3을 지울 수 있을 때 86512가 가장 큰 수입니다.

그런데 반례가 있습니다.

373865127라는 숫자가 있을 경우, 맨 앞자리 3은 잘 지우겠지만 7은 지워지지 않습니다.

그런데 만일 지울 수 있는 수에 3과 7이 추가적으로 남아있는 경우 맨 앞에 있는 373을 지운 865127이 정답이 됩니다.

하지만 1번의 논리대로 가면 7은 지울 수 없죠, 뒷자리에 있는 3보다 크니까요..

2. 작은 수는 앞에서 뒤로, 큰 수는 뒤에서 앞으로 지워나갑니다.

ex) 17571이 있을 때 1과 7을 지울 수 있다면 751이 정답입니다.

하지만 작은 수의 기준을 잡을 수 없을 뿐더러 이것 또한 반례가 있습니다.

79575가 있고, 7과 5를 한 번씩 지울 수 있다고 하면,

7이 5보다 크지만 맨 앞에 있는 7을 지운 975가 정답이 됩니다.

위 2가지 방법 외에도 많은 방법을 시도해봤지만 모두 실패하였고 접근을 달리했습니다.

지우는 쪽으로 가지 말고 '사용 가능한 숫자를 나열하자'

어차피 지우라고 준 숫자는 모두 지워야 합니다. 그렇다면 지울 숫자를 모두 빼버립니다.

그리고 사용해야 하는 숫자들 중 큰 숫자부터 배열합니다.

물론 숫자의 순서는 정해져있어서 마음대로 나열하면 안 됩니다.

그러면 도대체 어쩌라는 것이냐?

먼저, 사용할 수 있는 숫자 중 가장 큰 숫자를 먼저 배치합니다.

그리고 그 숫자 뒤로 남은 사용할 숫자들을 모두 배치할 수 있는지 보는 거죠.

남은 숫자들을 어떻게 배치할 것인가는 고려할 필요가 없습니다. 그냥 어떻게든 배치할 수 있으면 됩니다.

어차피 숫자의 길이는 일정하기 때문에, 앞 자리가 크면 그냥 큰 숫자가 되기 때문이죠.

방법만 들어서는 무슨 말인지 잘 모르겠으니 예를 들어봅시다.

예제 입력 6번을 예로 들어보죠.

2654982765982365
2345978

주어진 숫자에는 9가 2개, 8이 2개, 7이 1개, 6이 3개, 5가 3개, 4가 1개, 3이 1개, 2가 3개 있습니다.

지울 숫자에는 9,8,7,5,4,3,2가 1개씩 있습니다.

따라서 사용해야 할 숫자는 9가 1개, 8이 1개, 6이 3개, 5가 2개, 2가 2개입니다.

9:1, 8:1, 6:3, 5:2, 2:2

2654982765982365

9:1, 8:1, 6:3, 5:2, 2:2

사용해야 할 숫자 중 가장 큰 숫자는 9입니다.

일단 제일 앞 자리부터 스캔해보겠습니다.(왜냐하면 가능한 제일 앞 자리에 숫자를 넣었는데, 나머지 숫자들을 배치할 수 없다면, 어차피 뒷 자리에 숫자를 넣는다 하더라도, 지금 당장은 나머지 숫자를 모두 배치할 수 없기 때문입니다.)

그럼 4번째 인덱스에 9를 넣을 수 있습니다.(0번째 인덱스부터 시작했습니다.)

그러면 뒤쪽에 나머지 숫자들을 배치할 때 6을 1개 배치할 수 없습니다. 따라서 9를 제일 앞쪽에 배치할 수 없습니다.

2654982765982365

9:1, 8:1, 6:3, 5:2, 2:2

그럼 그 다음 큰 숫자인 8을 배치해보죠.

5번째 인덱스에 배치할 수 있군요, 하지만 역시 6을 1개 배치할 수 없기 때문에 불가능 합니다.

2654982765982365

9:1, 8:1, 6:3, 5:2, 2:2

그럼 그 다음 큰 숫자인 6을 먼저 배치해보죠.

1번째 인덱스에 배치할 수 있습니다. 그리고 그 뒤로 나머지 숫자들을 쭉 배치할 수 있습니다.

배치가 가능해서 6을 배치하겠습니다. 숫자는 이제 6으로 시작해야 하니까 시작 인덱스는 0이 아니라 2가 됩니다.

2654982765982365

9:1, 8:1, 6:3, 5:2, 2:2

다시 제일 큰 수인 9를 배치해보겠습니다.

2번 인덱스부터 스캔을 시작해보고, 4번 인덱스에 배치할 수 있고 이번에는 그 뒤로 나머지 숫자들을 쭉 배치할 수 있습니다.

그래서 9를 배치하겠습니다. 이제 시작 인덱스는 5가 되겠습니다.

이런 식으로 쭉 배치해나가면 정답을 구할 수 있습니다.

그런데 글을 읽다보면 배치가 가능한걸 어떻게 구현하지..? 하는 생각이 드실 수 있습니다.

고민하실 필요 없습니다. 위에서 제가 어떻게 배치하는 지는 상관 없다고 했습니다.

숫자는 앞자리가 클 수록 크니까요.

그러니까 뒷 자리에 남아있는 숫자별 개수가 지워야할 숫자별 개수보다 많으면 됩니다.

파이썬에서는 Counter를 쓰면 편하겠군요.

배치할 숫자마다 수 전체를 스캔하니 시간복잡도는 O(N^2)이 되겠습니다.

코드입니다.

import sys;
from collections import Counter

seq = input().strip()
R = input().strip()
cnt = Counter(seq) - Counter(R)
ans = ''
idx = 0
while cnt:
    for i in range(9, -1, -1):
        num = str(i)
        if cnt[num] < 1:
            continue
        t = seq.find(num, idx)  # 이 수가 들어갈 자리 확인
        # 마지막으로 채워넣은 수 다음 자리부터 찾아야 해서 idx를 넣음
        check = cnt - Counter(seq[t:])  # 남은 애들을 뒤에 있는 숫자들에 채워넣을 수 있는지 확인
        if check:  # 여기에 숫자를 배치하면 뒤에 애들로 남은 숫자들을 배치할 수 없는 경우
            continue
        else:
            ans += num
            idx = t + 1
            cnt[num] -= 1
            if cnt[num] == 0:
                del cnt[num]
            break  # 다시 제일 큰 수부터 찾아야 올바르게 찾을 수 있다.

print(ans)

최대한 풀어쓴다고 많이 썼는데 이해에 도움이 되었는지 모르겠습니다.

방법 자체는 별 거 없는데.. 떠올리기 참 힘들어서 플래티넘 2를 받은게 아닌가 싶습니다.

사실 저는 요즘 Greedy와 DP는 알고리즘을 빙자한 아이큐 테스트가 아닌가 하는 생각이 듭니다.

문제해결을 하는 방법을 제시하긴 하지만 그것만으로는 별 도움이 안 되는..

방법 자체를,점화식 자체를 떠올려야 하는..

그래도 알고리즘 문제풀이 재밌네요.

이걸 좀 일찍 알았다면 준비 열심히 해서 ICPC도 도전해봤을 텐데.. 아쉽습니다.

그래도 제가 배웠던 것들, 연습하고 준비했던 것들이 언젠간 제게 도움이 되겠죠.

열심히 살아야겠습니다.

백준 greedy 26 view 1301