[백준 / Python] 14370번 전화번호 수수께끼 (Large)

 

문제

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

---

코드

import sys
input = sys.stdin.readline 

n = int(input())

data = {
    'A':0,
    'B':0,
    'C':0,
    'D':0,
    'E':0,
    'F':0,
    'G':0,
    'H':0,
    'I':0,
    'J':0,
    'K':0,
    'L':0,
    'M':0,
    'N':0,
    'O':0,
    'P':0,
    'Q':0,
    'R':0,
    'S':0,
    'T':0,
    'U':0,
    'V':0,
    'W':0,
    'X':0,
    'Y':0,
    'Z':0
}

for i in range(n):
    answerlist = [0] * 10
    txt = input().rstrip()
    for c in txt:
        data[c] += 1
    while data['Z'] > 0:
        data['Z'] -= 1
        data['E'] -= 1
        data['R'] -= 1
        data['O'] -= 1
        answerlist[0] += 1
    while data['W'] > 0:
        data['T'] -= 1
        data['W'] -= 1
        data['O'] -= 1
        answerlist[2] += 1
    while data['U'] > 0:
        data['F'] -= 1
        data['O'] -= 1
        data['U'] -= 1
        data['R'] -= 1
        answerlist[4] += 1
    while data['X'] > 0:
        data['S'] -= 1
        data['I'] -= 1
        data['X'] -= 1
        answerlist[6] += 1
    while data['G'] > 0:
        data['E'] -= 1
        data['I'] -= 1
        data['G'] -= 1
        data['H'] -= 1
        data['T'] -= 1
        answerlist[8] += 1
    while data['O'] > 0:
        data['O'] -= 1
        data['N'] -= 1
        data['E'] -= 1
        answerlist[1] += 1
    while data['R'] > 0:
        data['T'] -= 1
        data['H'] -= 1
        data['R'] -= 1
        data['E'] -= 2
        answerlist[3] += 1
    while data['F'] > 0:
        data['F'] -= 1
        data['I'] -= 1
        data['V'] -= 1
        data['E'] -= 1
        answerlist[5] += 1
    while data['S'] > 0:
        data['S'] -= 1
        data['E'] -= 2
        data['V'] -= 1
        data['N'] -= 1
        answerlist[7] += 1
    while data['E'] > 0:
        data['N'] -= 1
        data['I'] -= 1
        data['N'] -= 1
        data['E'] -= 1
        answerlist[9] += 1
    print("Case #%d:" % (i + 1), end=" ")
    for i in range(10):
        print(str(i) * answerlist[i], end="")
    print()

 

 

---

 

해설

위 문제를 풀면 

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

같은 코드로 14369번 전화번호 수수께끼 (small) 도 풀 수 있습니다. 

 

이 문제는 특별한 특징만 찾으면 그리디하게 풀 수 있습니다. 

 

다음은 0부터 9까지의 스펠링입니다. 

0: Zero
1: One
2: Two
3: Three
4: Four
5: Five
6: Six
7: Seven
8: Eight
9: Nine

 

위에서 잘보면 six에만 x가 존재한다는 걸 알 수 있고 

주어진 문자에 x 알파벳이 n개 있다면 six가 n개 있다는 것을 알 수 있습니다. 

 

위처럼 특별한 문자가 있는 숫자는 다음과 같습니다. (신기하게 짝수만 존재하네요?) 

0: Z (Zero)
2: W (Two)
4: U (Four)
6: X (Six)
8: G (Eight)

 

one은 o가 two에 존재하고 n이 nine에 존재하고 e가 seven에 존재하기에 특별한 알파벳이 있는 숫자들을 모두 제거하고 다시 특징을 찾아봐야합니다

 

1: One -> O
3: Three -> T
5: Five -> F
7: Seven -> S
9: Nine -> N 

 

짝수들을 처리하고 홀수를 처리하면 이 문제를 풀 수 있습니다.