반응형
문제
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
짝수들을 처리하고 홀수를 처리하면 이 문제를 풀 수 있습니다.
반응형
'Programming > 알고리즘' 카테고리의 다른 글
[백준 / Python] 18917번 수열과 쿼리 38 (1) | 2024.06.10 |
---|---|
[백준 / Python] 11000번 강의실 배정 (0) | 2024.05.29 |
[백준 / Python] 7576번 토마토 (1) | 2024.05.08 |
[백준 / Python] 1015번 수열 정렬 (0) | 2024.03.28 |
[백준/Python] 17219번 비밀번호 찾기 (0) | 2024.02.27 |
댓글