[백준] 16496번 - 큰 수 만들기

📩 출처

문제

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

👉 생각

• 주어지는 숫자들을 number 배열에 담고 stack 이라는 배열을 생성해서 number[0]을 담아준다. 이후 number[1]부터 하나씩 꺼내서 스택에 있는 마지막 값과 비교를 한다. 여기서 비교란, 두 값중 우선순위가 있는, 더 앞에 나와야 하는 값을 스택에 마지막에 넣어준다.
• number[i]가 stack에서 꺼낸 값보다 우선순위가 없다면 stack에 있는 값들과도 우선순위 비교를 해주어야한다. 비교를 해주면서 stack에 값을 채워나가고 number의 모든 값을 확인하면 적절하게 출력하면 된다.

import sys
n = int(input())
number = list(sys.stdin.readline().split())
stack = [number[0]]

# 일단 스택에 다 넣자, 스택을 항상 갱신하자!
for i in range(1, n):
    tmp = stack.pop()
    # 스택에서 빼낸 값보다 현재 값이 더 우선순위가 있다면
    if int(tmp + number[i]) <= int(number[i] + tmp):
        stack.append(tmp)
        stack.append(number[i])
    # 스택 갱신, 스택에서 빼낸 값이 더 우선순위가 있음
    else:
        # 스택에 값이 있다면 갱신해주고
        check = []
        if stack:
            while stack:
                last_value = stack.pop()
                if int(last_value + number[i]) < int(number[i] + last_value):
                    stack.append(last_value)
                    break
                else:
                    check.append(last_value)
            stack.append(number[i])
            if check:
                check.reverse()
                stack.extend(check)
            stack.append(tmp)
        # 스택이 비어 있다면
        else:
            stack.append(number[i])
            stack.append(tmp)
stack.reverse()
answer = ''.join(stack)
print(0) if answer[0] == '0' else print(answer)

• stack을 사용해도 되지만 정렬을 통해 다음과 같이 구할 수도 있다.

n = int(input())
number = input().split()
number.sort(key = lambda x: x*10)
answer = ''.join(number[::-1])
print(0) if answer[0] == '0' else print(answer)