[Swift] 알고리즘 공부 - 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 떄, 정수를 이어 붙여 만ㄷ르 수 있는 가장 큰수를 알아내 주세요.

예를 들어, 주어징 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해 주세요.

 

제한사항

• numbers의 길이는 1이상 100,000 이하입니다.
• numbers의 원소는 0이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

입출력 예

numbers                                                                                          return

[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

 

설명

1. 수를 조합해서 가장 큰 수를 만들기 위해서 비교 클로져를 사용한다.

2. 만약 [1,3,2]라는 배열이 있으면 1과 3을 두고 조합하여 13, 31중 13이 크므로 [3,1,2]로 정렬이 된다. 이걸 반복하게되면 [3,2,1]이 나오고 [1,3,2]를 조합해서 가장 큰 수가 나오는 수는 321이 된다.

3. reduce로 정렬된 값을 조합한다 이때 맨 앞자리가 0이 나올 수 있기 때문에 삼항연산자로 맨앞에 0이 오는 것을 제외해 준다.

import Foundation

func solution(_ numbers:[Int]) -> String {
    return numbers.sorted {
        let s1 = String($0)
        let s2 = String($1)
        
        return s1+s2 > s2+s1
    }.reduce("") { 
        $0 != "0" ? $0 + String($1) : String($1) 
    }

}

 

처음 문제를 접근할 때 가장 큰수를 찾기 위해서는 조합하여 만들 수 있는 모든 수를 배열에 저장한 후 정렬해서 가장 큰수를 찾으려고 했지만 위의 방식으로 접근할 수 있어서 다른 방식을 사용하였다.