[Algorithm] 프로그래머스 가장 큰 수

문제 설명

나의 풀이 - 1

import Foundation
func solution(_ numbers:[Int]) -> String {
    let numbers = numbers.map { String($0) }
    var visit: [Bool] = [Bool](repeating: false, count: numbers.count)
    let answer = ""
    var possibles = [String]()

    dfs(data: numbers, visit: &visit, curInd: 0, curCnt: 0, targetCnt: numbers.count, answer: answer, possibles: &possibles)

    let intPossibles = possibles.map { Int($0)! }.sorted(by: >)
    return "\(intPossibles[0])"
}

func dfs(data: [String], visit: inout [Bool], curInd: Int, curCnt: Int, targetCnt: Int, answer: String, possibles:inout [String]) {
    if curCnt == targetCnt {
        possibles.append(answer)
        return
    }

    for i in 0..<data.count {
        if !visit[i] {
            visit[i] = true

            dfs(data: data, visit: &visit, curInd: i, curCnt: curCnt + 1, targetCnt: targetCnt, answer: answer + data[i], possibles: &possibles)
            visit[i] = false
        }
    }
}

순열을 사용해서 해당 개수로 만들 수 있는 모든 개수를 만들고 정렬하여 가장 큰 수를 출력하도록 했지만 이 방법의 경우에는 시간 초과가 발생하게 된다.

고민한 점

이후 문제를 해결하기 위해서 다음과 같은 과정으로 해결해보려고하였다.

1. 정렬을 하는데 앞자리가 제일 큰 수자가 맨 앞에
2. 앞자리가 같지만 자리수가 다른 경우
3. 각각의 자리수와 비교하여 더 큰 수가 앞으로 가도록

그러나 이렇게 구현을 해보려고했는데, 문제는 각각의 자리수에 숫자가 몇개나 있는지 그리고 두자리수와 세자리수의 비교, 두자리와 네자리수의 비교 등은 구현하기에 너무 복잡해서 구글링을 해보았다.

해결 풀이

import Foundation
func solution(_ numbers:[Int]) -> String {
    let numbers = numbers.sorted(by: { Int("\($0)\($1)")! > Int("\($1)\($0)")!})
    if numbers[0] == 0 {
        return "0"
    }
    
    return numbers.reduce("") { $0 + "\($1)" }
}

뒤통수를 맞은 기분이였다.. 숫자 두 개를 순서를 바꿔서 붙여보고 둘 중에 큰걸로 정렬을 하도록 하게하면 문제가 해결되었다…

그리고 예외사항으로는 [0,0,0,0] 과 같이 정렬이후 첫 번째 원소가 0으로 이루어진 경우에는 0000이 정답으로 나오지 않게 처리해준다.

참고

Programmers
유쾌한 가장 큰 수