[Swift] 백준 10972 - 다음 순열

문제 바로가기

처음엔 재귀함수와 백트래킹을 사용해서 풀었는데
print횟수를 줄이고, map 을 줄이는 등
뭐를 해도 시간초과가 나기에 이 풀이는 안되는거구나 했다...

시간 초과된 풀이

import Foundation

let n = Int(readLine()!)!
let nArray = readLine()!.split(separator: " ").map {Int(String($0))!}

var result = [Int]()
var mode = false
var printResult = ""

recur()

func recur() {
    if result.count == n {
        if mode {
            printResult += result.map{String($0)}.joined(separator: " ")
            mode = false
        }
        
        if result == nArray {
            mode = true
        }
        return
    }
    
    for i in 1...n {
        if !result.contains(i) {
            result.append(i)
            recur()
            result.popLast()!
        }
    }
}

if printResult.isEmpty {
    print(-1)
} else {
    print(printResult)
}

• 답은 제대로 나왔는데...🥲

아무튼 그래서 다른 분들의 해설을 보고 다른 방법을 이해했다

예를 들어,
N = 4이고 주어진 순열이 [2,1,4,3] 라고 할 때
다음 순열은 [2,3,1,4] 이다.

이 다음 순열을 구하는 순서는 다음과 같다.

i가 0부터 N-1까지 있을 때

1. nArray[i-1] < nArray[i] 를 만족하는 가장 큰 자릿수 i를 구하고
   • [2,1,4,3] 에서 i 는 2(세번째 원소) 이다
2. nArray[i-1] < nArray[j] 를 만족하는 가장 큰 자릿수 j를 구한 뒤
   • [2,1,4,3] 에서 j는 3(네 번째 원소)
3. nArray[i-1]과 nArray[j] 의 원소를 swap 한 뒤
   • [2,1,4,3] -> [2,3,4,1]
4. nArray[i] 부터 배열을 뒤집는다
   • [2,3,4,1] -> [2,3,1,4]

이 과정을 코드로 구현하면

최종 풀이

import Foundation

let n = Int(readLine()!)!
var nArray = readLine()!.split(separator: " ").map {Int(String($0))!}


if Array(1...n).reversed() == nArray {
    print("-1")
} else {
    outerLoop: for i in (0..<n).reversed() {
        if nArray[i-1] < nArray[i] {
            for j in (0..<n).reversed() {
                if nArray[i-1] < nArray[j] {
                
                    nArray.swapAt(i-1, j)
                    nArray = nArray[...(i-1)] + nArray[i...].reversed()
                    
                    print(nArray.map{String($0)}.joined(separator: " "))
                    break outerLoop
                }
            }
        }
    }
}