정렬_Programmers_가장 큰 수 [Swift]

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=swift

프로그래머스

 

풀어보려고 눌렀더니, 과거 기록이 있던 문제.

이번에도 자력으로 푸는데 실패했다.

 

접근 방법

1. numbers의 숫자를 선택하는 순서는 무관하므로, 뒤에서부터 원소를 꺼낸다.
2. queue가 빌때까지 반복한다.
3. queue의 마지막 원소를 꺼내고 solArray의 insert하는 모든 경우를 만들어내어 posibles에 저장한다.
4. posibles의 각 원소를 joined하여 ["1","3","2"] 형태를 "132"로 바꾼다. joined는 ["132","312","231"]의 형태가 된다.
5. index별 숫자를 비교하여 정렬한다

오답 코드

func solution(_ numbers:[Int]) -> String {
    var reversedQueue = numbers.map { "\($0)" }
    var solArray = [reversedQueue.removeLast()]
    
    while !reversedQueue.isEmpty {
        let target = reversedQueue.removeLast()
        var posibles = [[String]]()
        for i in 0...solArray.count {
            var temp = solArray
            temp.insert(target, at: i)
            posibles.append(temp)
        }
        // print(posibles.map { $0.joined()})
        let joined = posibles.map { $0.joined()}
        var max = joined.sorted(by: { lhs, rhs in
            // Int($0)! < Int($1)! overflow난다
            // 각 자릿수를 비교한다.
            var isLeftSmall = true
            for index in lhs.indices {
                if lhs[index].wholeNumberValue! == rhs[index].wholeNumberValue! { continue }
                else {
                    isLeftSmall = lhs[index].wholeNumberValue! < rhs[index].wholeNumberValue!
                    break
                }
            }
            return isLeftSmall
        }).last!
        let maxIndex = joined.firstIndex(of: max)!
        solArray = posibles[maxIndex]
    }
    
    return solArray.joined()
    
}

오답 코드 성능

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	통과 (1.90ms, 16.7MB)
테스트 8 〉	통과 (0.75ms, 16.8MB)
테스트 9 〉	통과 (1.56ms, 16.6MB)
테스트 10 〉	통과 (0.71ms, 16.7MB)
테스트 11 〉	실패 (102.57ms, 16.8MB)
테스트 12 〉	통과 (0.18ms, 17MB)
테스트 13 〉	통과 (0.22ms, 16.9MB)
테스트 14 〉	통과 (0.29ms, 16.6MB)
테스트 15 〉	통과 (0.20ms, 16.8MB)

정답 코드

func solution(_ numbers:[Int]) -> String {
    var nb = numbers.map { "\($0)" }
    let sorted = nb.sorted(by: { 
        // Int($1+$0) < Int($0+$1)
        $1 + $0 < $0 + $1
    })
    
    return sorted.first == "0" ? "0" : sorted.joined()
}

정답 코드 풀이

예제: [3, 30, 34, 5, 9]

 

1️⃣ “3”과 “30” 비교

 

우리는 "3" + "30" = "330" 과 "30" + "3" = "303" 을 비교한다.

“330” > “303” 이므로 "3"이 "30"보다 앞에 와야 한다.

 

2️⃣ “34”와 “3” 비교

 

우리는 "34" + "3" = "343" 과 "3" + "34" = "334" 을 비교한다.

“343” > “334” 이므로 "34"가 "3"보다 앞에 와야 한다.

 

3️⃣ “5”와 “34” 비교

 

우리는 "5" + "34" = "534" 과 "34" + "5" = "345" 을 비교한다.

“534” > “345” 이므로 "5"가 "34"보다 앞에 와야 한다.

 

4️⃣ “9”와 “5” 비교

 

우리는 "9" + "5" = "95" 과 "5" + "9" = "59" 을 비교한다.

“95” > “59” 이므로 "9"가 "5"보다 앞에 와야 한다.

 

숫자 정렬이 아니라 문자비교를 하는 이유

1. overflow 방지

2. 사전순 정렬을 위하여. 

 

정답 코드 성능

테스트 1 〉	통과 (270.35ms, 21.5MB)
테스트 2 〉	통과 (154.74ms, 18.8MB)
테스트 3 〉	통과 (459.70ms, 22.6MB)
테스트 4 〉	통과 (5.68ms, 16.3MB)
테스트 5 〉	통과 (357.98ms, 20.7MB)
테스트 6 〉	통과 (271.04ms, 20.2MB)
테스트 7 〉	통과 (0.15ms, 16.1MB)
테스트 8 〉	통과 (0.21ms, 16.3MB)
테스트 9 〉	통과 (0.12ms, 16.3MB)
테스트 10 〉	통과 (0.13ms, 16.3MB)
테스트 11 〉	통과 (0.11ms, 16.4MB)
테스트 12 〉	통과 (0.15ms, 16.2MB)
테스트 13 〉	통과 (0.12ms, 16.6MB)
테스트 14 〉	통과 (0.21ms, 16.4MB)
테스트 15 〉	통과 (0.15ms, 16.5MB)