<문제 179. Largest Number>
Given a list of non-negative integers nums, arrange them such that they form the largest number.
Note: The result may be very large, so you need to return a string instead of an integer.
음이 아닌 정수 리스트 nums이 주어지면 가장 큰 수를 구성하도록 정렬하세요.
참고: 결과가 매우 클 수 있으므로 정수 대신 문자열을 반환해야 합니다.
<예시>
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Example 3:
Input: nums = [1]
Output: "1"
Example 4:
Input: nums = [10]
Output: "10"
주어진 예시들을 보면
입력이 10, 2라면 이 요소들로 구성할 수 있는 수는 102와 210이 되고
가장 큰수는 210이므로 문자열로 반환합니다
두 번째 예시도 마찬가지로 다섯 개의 요소를 조합했을 때 구성할 수 있는 가장 큰 수를 문자열로 반환합니다.
리스트의 요소가 하나이면 그 요소 그대로 반환합니다.
이 문제는 String/ Greedy/Sorting 관련 문제라고 주어져있고
저는 버블 정렬을 사용해서 문제를 풀었습니다
<Bubble Sorting (버블정렬)>
선택졍렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는 정렬입니다
제일 큰 원소를 오른쪽으로 옮기면서 정렬이 됩니다
아래는 버블 정렬의 알고리즘입니다.
#1~N을 원소로 가진 Array 리스트를 정렬
bubble sort(Array[1~n], n)
for last = n 부터 2
for i = 1부터 last-1
if( Array[i] > Array[i+1])
Array[i]와 Array[i+1] 원소 교환
알고리즘은 크게 두 개의 for loop로 이루어져 있습니다
첫 번째 for loop는 루프를 돌 때마다 맨 오른쪽에 있는 가장 큰 원소를 제외하고 정렬할 배열의 크기를 하나씩 줄입니다.
두 번째 for loop는 가장 큰 원소를 맨 오른쪽으로 보내고 조건문을 통해
왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어있지 않으면 하나하나 바꾸어 나갑니다.
<Largest Number 문제에 Bubble Sort 적용>
리스트 차례대로 두 개씩 원소를 조합하고 그 수를 비교한 다음
더 큰 조합이 나오도록 원소를 오른쪽으로 옮기는 방법을 사용해서
리스트를 하나로 합쳤을 때 가장 큰 수가 나오도록 정렬하였습니다.
<그림으로 이해하기>
nums = [3,30,34,5,9]이 입력인 경우를 예로 들어 과정을 살펴보겠습니다.
리스트의 모든 원소를 순서대로 합쳤을 때, 가장 큰 수가 만들어지도록 리스트를 정렬하기 위해서
현재 요소에 뒤의 요소를 붙인 값과 뒤의 요소에 현재 요소를 붙인 값을 비교합니다
앞의 경우가 더 크다면 두 원소의 순서는 바꾸지 않고 그대로 둡니다
그리고 그다음 원소로 넘어가서 현재 요소와 그 다음 요소를 조합한 값들을 비교합니다.
뒤의 요소에 현재 요소를 붙인 값이 더 크다면 두 개의 순서를 바꾸는 것이 목적에 맞게 정렬되는 것이므로 두개의 요소를 교환해 줍니다.
위와 같은 방법으로 리스트 끝까지 반복합니다.
이렇게 첫 번째 반복이 끝났습니다
리스트의 맨 오른쪽 요소인 30은 고정이 되고
다음 반복에서는 제외됩니다.
그리고 두 번째 반복을 진행합니다
여기서 '첫 번째 반복 두번째 반복...'의 과정은 은 버블 정렬의 첫번째 for loop이고..
리스트의 왼쪽부터 마지막까지 순서대로 확인하고 교환해주는 과정은 버블 정렬의 두 번째 for loop와 if문이 적용됩니다.
앞의 작업을 반복하면서 계속 맨 오른쪽 요소를 제외해나갑니다
마지막으로 두 개 짜리의 배열의 처리가 끝나면 정렬이 완료됩니다.
<Pseudo Code>
위의 방법을 수도 코드로 작성하면 다음과 같습니다
<Python Code>
파이썬으로 구현한 코드입니다.
class Solution(object):
def largestNumber(self, nums):
for i in range(len(nums), 0 , -1):
for j in range(0, i-1):
if not self.compare(nums[j], nums[j+1]):
nums[j], nums[j+1] = nums[j+1], nums[j]
return str(int("".join(map(str, nums))))
def compare(self, n1, n2):
return str(n1) + str(n2) > str(n2) + str(n1)