[알고리즘] BOJ 20915 숫자 카드 놀이

[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)