[파이썬] 백준 14369,14370 전화번호 수수께끼

일반적으로 접근한다면 백트래킹이 어울릴법한 풀이다.
하지만 분류가 에드 혹 (일반화 할 수 없는 해결책 이라는 뜻) 이기 때문에 차분히 적어보면서 풀어보았다.
좀 불만인것은 힌트 로 주어진 부분이 문제 안에 들어가야 되는게 맞지않나 싶다.
맨처음에 힌트를 보지 않아서 문제를 이해하는데 어려웠다.

0~9를 영어로 적어보면

0 : ZERO
1 : ONE
2 : TWO
3 : THREE
4 : FOUR
5 : FIVE
6 : SIX
7 : SEVEN
8 : EIGHT
9 : NINE

이다.
이중에서 어느 한 숫자만이 가지고 있는 철자를 뽑아보았다.
예를 들어 0은 Z, 6은 X, 그리고 8은 G를 유일하게 가지는 숫자이다.
이 숫자들을 먼저 문자열에서 소거해보자.

그렇게 된다면 SIX 의 S때문에 사용하지 못했던 SEVEN의 S를 사용할 수 있다.
이후 마찬가지로 SEVEN 의 V때문에 사용하지 못했던 FIVE의 V를 사용할 수 있다.

이런식으로 하나씩 소거해나가면
0,6,8,7,5,4,9,2,3,1 순서대로 완벽하게 소거할 수 있다.

해당 아이디어를 코드로 옮기면

from collections import defaultdict
A=[('Z','ZERO',0),('X','SIX',6),('G','EIGHT',8),
('S','SEVEN',7),('V','FIVE',5),('F','FOUR',4),
('I','NINE',9),('W','TWO',2),('R','THREE',3),
('O','ONE',1)]
for t in range(int(input())):
    d=defaultdict(int)
    arr=[0]*10
    for c in input():d[c]+=1
    for k,v,i in A:
        if d[k]>0:
            arr[i]=d[k]
            for c in v: d[c]-=arr[i]
        arr[i]=str(i)*arr[i]
    print(f"Case #{t+1}: {''.join(arr)}")

같이 풀 수 있다.

for c in input():d[c]+=1 에서 입력으로 들어오는 문자의 철자 별 갯수를 d에 저장해준다.
예를 들어 입력이 ABBBCC 였다면

d={
	'A' : 1,
    'B' : 3,
    'C' : 2,
}

과 같이 저장될 것이다.

이후
for k,v,i in A: 부분에서 소거를 하고 arr에 출력될 문자열을 담아준다.

코드 량 대비 괜찮은 수행시간이 나온 것 같아 만족스럽다.