[BOJ] 20915 숫자 카드 놀이 바로가기
Albert 는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지 숫자 하나씩이 적혀있고, 6이나 9가 적힌 카드를 회전할 경우 구분할 수 없다 (즉, 6이 적힌 카드는 회전하면 9로 보이고, 9가 적힌 카드는 회전하면 6으로 보인다).
Albert는 최근 두 수의 곱셈에 대해 배운터라 n장의 카드를 모두 이용하여 두 개의 수를 만든 후, 그 수의 곱이 최대가 되도록 하고 싶다. 단, n장의 카드 모두 사용하여야 하며, 각 수는 최소 1장 (그리고 최대 n-1장)의 카드로 구성되어야 한다. 6이나 9가 적힌 카드는 Albert가 임의로 회전하여 사용할 수 있다.
예를 들어 n = 8이고 Albert가 가진 카드가 [2, 0, 2, 0, 2, 0, 2, 1] 이라 하자. 이 때 8장의 카드를 활용하여 "2200" 과 "2210"을 만들면 두 수의 곱은 4862000이 된다. 혹은 "2020"과 "2021"을 만들어 곱이 4082420이 되도록 할 수도 있다. 이 예제에서 Albert가 만들 수 있는 최대 곱은 4862000이다.
입력으로 Albert가 가진 n장의 숫자 카드가 주어졌을 때, 달성 가능한 최대 곱을 구하시오.
첫 줄에 테스트 케이스의 수 T가 주어진다.
다음 각 줄에 Albert가 가진 숫자 카드를 표현하는 문자열이 (공백없이) 주어지는데, 문자열의 각 문자는 '0'-'9' 중 하나이다.
각 테스트 케이스에 대해 Albert가 만들 수 있는 최대 곱을 출력한다.
✍ 코드
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
n = list(map(int,stdin.readline().rstrip()))
N = []
zero = 0 # 숫자 0 의 갯수
for i in range(len(n)): # 숫자 6을 9로 변환
if n[i] == 6:
n[i] = 9
for num in n:
if num == 0: # 숫자 0의 갯수 count
zero += 1
else: # 0 의외의 숫자 검열
N.append(num)
if len(n) == zero: # 모든 숫자의 값이 0일 경우
print(0)
continue
N.sort(reverse=True) # 내림차순으로 정렬
a = N[0]
b = 0
for i in range(1,len(N)):
if a > b: # a의 값이 클 경우
b = b * 10 + N[i]
else: # b의 값이 클 경우
a = a * 10 + N[i]
for _ in range(zero):
a *= 10
print(a*b)