[백준][파이썬] 20915번 : 숫자 카드 놀이 (코드, 해설, 풀이)

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

20915번: 숫자 카드 놀이

 

 

---

- 문제

숫자 20202021이 주어지면 이걸 2와 221000으로 나눈 후 곱하던지, 2200과 210으로 나눈 후 곱해서 결과가 더 큰 숫자를 출력한다는 것이다. 종이에 먼저 적어보고 알고리즘을 생각한 다음에 풀면 어렵지 않게 풀 수 있었을 것 같은데, 코드를 먼저 작성하고 문제를 풀어서 조금 어렵게 풀었던 것 같다.

 

---

- 해설

  0의 개수는 따로 빼고 문제를 풀어야 한다는 것을 생각해야 한다. n을 a와 b 두 개로 나눈다고 했을 때, n이 20202021이어서 0이 3개이면, a에 0을 3개 추가하는거랑 b에 0을 3개 추가하는거랑, a에 2개 b에 1개, 혹은 a에 1개 b에 2개 주는거 모두 결국에는 값이 똑같아진다는 것을 알아야한다. 22000 * 21, 22 * 21000, 2200 * 210, 그리고 220 * 2100 모두 똑같은 값을 나타낸다. 

 

  이제 123이 주어졌을 때 이걸 큰 수부터 정렬해서 321로 만들고 a에 3을 준 후 b에 2를 분배하고 나머지 1을 어디에 분배할지를 생각해야 한다. 31 * 2 = 62, 3 * 21 = 63이고 123말고 다른 숫자를 해보더라도 더 작은 숫자에 분배를 했을 때 최종적으로 더 큰 값이 나온다는 것을 확인할 수 있을 것이다. 

 

  103020이 주어지면 0의 개수를 파악해서 저장하고, 정렬해서 321만 남기도록 한다. 이후 321을 적절히 분배하고 마지막에 a 혹은 b에 파악한 0의 개수만큼 추가해주면 끝나는 문제다.

 

  모든 6을 9로 바꿀 수 있고, 9보다 6을 썼을때 더 큰수가 나오는 경우는 없으므로 6을 모두 9로 바꿔주는 부분도 추가해야 한다.

---

- 풀이

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    b = 0
    n = list(map(int, sys.stdin.readline().rstrip()))
    zeros = n.count(0)
    for i in range(len(n)):
        if n[i] == 6:
            n[i] = 9
    n.sort(reverse=True)
    for i in range(zeros):
        n.pop()
    if not(n):
        print(0)
        continue
    a = n[0]
    for i in range(1, len(n)):
        if a > b:
            b = b*10 + n[i]
        else:
            a = a*10 + n[i]
    for i in range(zeros):
        a *= 10
    print(a*b)

  가장 먼저 0의 개수를 zeros에 넣고, 모든 6을 9로 변경 후 내림차순으로 정렬한다. 정렬 후에는 모든 0이 배열의 가장 뒷부분에 있으므로 zeros의 크기만큼 pop을 해주면 0이 모두 사라지게 된다. 만약 모든 숫자가 0이면 n은 빈 배열이 될 것이므로 0을 출력하게 하고 끝내도록 한다. 이후에 a에 첫 번째 수를 넣어주고 반복문을 두 번째 숫자부터 시작해서 a와 b를 비교해 더 작은 수에 10을 곱한 후 숫자를 추가하도록 한다.

  마지막에 zeros의 개수만큼 10을 곱해주면 정답을 구할 수 있다.