[ 9440 ] [ Greedy ] 숫자 더하기

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

9440번: 숫자 더하기

 

---

풀이 과정

---

1. 그리디 알고리즘 문제인데 처음 생각할 때 꼬여서 어떻게 풀어야 할지 고민을 정말 많이한 문제다ㅜ
2. 숫자를 오름차순으로 정렬한다.
   1. 숫자들로 두개의 정수를 만들어야 하므로 a, b 리스트를 만들어 둔다.
   2. a, b 리스트에 번갈아가면서 작은 숫자부터 넣어준다.
   3. a, b 리스트에서 맨 앞에 넣을때는 0이 아닌 수중에 가장 작은 숫자를 넣어주어야 한다.
   4. 리스트에 채우는 작업이 종료되면, 두 리스트를 정수화하여 더해주면 된다.
3. 더해준 값을 출력한다.

---

 소스 코드

---

import sys
from collections import deque, defaultdict

input = lambda: sys.stdin.readline().rstrip()
while True:
    p = list(map(int, input().split()))
    numbers = defaultdict(lambda: 0)
    if p[0] == 0:
        break
    
    for n in p[1:]:
        numbers[n] += 1
    
    a = []
    b = []
    flag = True
    for i in range(p[0]):
        target = None
        if flag:
            target = a
        else:
            target = b
        for j in range(10):
            if len(target) == 0 and j == 0:
                continue
            if numbers[j] > 0:
                numbers[j] -= 1
                target.append(j)
                break
        flag = not flag

    print(int("".join(map(str, a))) + int("".join(map(str, b))))