[코테] 백준 그리디 16496번 문제

16496번 : 큰 수 만들기

문제 링크

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

문제 설명

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

입력

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

출력

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

문제 풀이

일단 배열을 입력받을 때 문자열로 저장하고, 내림차순으로 정렬한다. (반복문의 횟수를 줄이기 위해)

이후 모든 배열의 항목을 순회할 때 1번도 앞 뒤 자리를 바꾸지 않을때까지 앞 뒤 자리를 바꾼다.

N = int(input())

arr = list(input().split())
arr.sort(reverse=True)

while True : 
    for i in range(N-1) :
        if (int(arr[i] + arr[i+1])) < (int(arr[i+1] + arr[i])) : 
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp
            break
    else :
        break
        
print(int(''.join(arr)))