[프로그래머스] 가장 큰 수 / 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"

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

---

풀이 과정

정렬 기준은 배열을 순회할 때 나오는 원소들을 붙여서 비교하는 것으로 정했다.

예를들면, 0번째 인덱스에 12가 1번째 인덱스에 22가 들어있다면 0번째 인덱스 + 1번째 인덱스 이렇게 나열한 문자열은 1222가 될 것이고 거꾸로 1번째 인덱스 + 0번째 인덱스로 나열한 문자열은 2212가 될 것이다. 이렇게 각 붙인 문자열을 비교하여 내림차순으로 정렬했다.

 

// 제자리 삽입 정렬로 구현한 버전
import Foundation

func solution(_ numbers:[Int]) -> String {
    var result = numbers
    
    for i in (0..<numbers.count) {
        let tmp = result[i]
        var current = 0
        
        for j in (0..<i) {
            current = i - j - 1
            let s1 = String(result[current])
            let s2 = String(tmp)
            
            if s1 + s2 > s2 + s1 {
                current += 1
                break
            }
            
            result[current + 1] = result[current]
        }
        
        result[current] = tmp
    }
    
    return result.reduce("") { $0 + String($1) }
}

 

처음에 구현했을 때 제자리 삽입 정렬로 구현했지만 역시나 시간초과 + 케이스 11번 틀림이 떴다 ㅠ

정렬하는 부분을 기본 내장 sort로 바꾸고 다시 돌리니,

// 내장 sort로 바꾼 버전
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 + String($1) } // 이 부분
}

시간 초과는 해결되었다. 문제 조건을 다시 제대로 읽어보니 0이 들어오는 경우를 생각해보지 않았다. 

그래서 Int배열에서 결과 출력을 위한 String으로 바꿀 때(reduce) 기존String값에 맨 앞에 "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)
    }
}

 

 

최종코드2 (6/19에 다시품)

import Foundation

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

---

생각 정리

Swift로는 삽입 정렬을 짜본적이 없어서 시험삼아 시간복잡도가 O(n^2) 인 삽입 정렬로 풀어보았는데 역시나 시간초과가 떴다. 도중에 Swift에서 내장 정렬은 어떤 알고리즘을 채택하고 있는지 찾아보니 Swift5기준 inplace-IntroSort 에서 Timsort 로 변경되는 등 계속해서 바뀌고 있다는 걸 확인했지만 처음 들어보는 알고리즘들이라 일단 이름만 기억하기로 했다..