백준 - 순열의 순서 (1722)

let N = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let q = input[0]

// 각 자리 경우의 수 구하기
var F = Array(repeating: 1, count: N + 1)
for i in 1..<N {
    F[i] = F[i - 1] * i
}
F.reverse()

// 질의 수행
var visited = Array(repeating: false, count: N + 1)

if q == 1 { // k번째 순열 구하기
    var answer = ""
    var k = input[1]
    for i in 0..<N {
        var count = 1
        for j in 1...N {
            if visited[j] {
                continue
            }
            if k <= F[i + 1] * count {
                k -= F[i + 1] * (count - 1)
                answer += "\(j) "
                visited[j] = true
                break
            }
            count += 1
        }
    }
    print(answer)
} else { // 몇 번째 순열인지 구하기
    var answer = 1
    let p = Array(input[1...N])
    for i in 0..<N {
        let now = p[i]
        var count = 0
        for j in stride(from: 1, to: now, by: 1) {
            if !visited[j] {
                count += 1
            }
        }
        answer += F[i + 1] * count
        visited[now] = true
    }
    print(answer)
}

순열의 성질을 이용하는 문제이다. 일단 N자리의 순열을 만들 수 있는 경우의 수는 N!이다.

1. k번째 순열 구하기

네 자리의 순열을 만든다고 해보자. 그러면 첫 번째 숫자가 1인 순열 1 _ _ _ 을 만드는 경우의 수는 3!이다. 마찬가지로 첫 번째 숫자는 1, 두 번째 숫자는 2인 순열 1 2 _ _ 을 만드는 경우의 수는 2!이 된다.

여기서 3번째 순열을 구하려면 어떻게 해야 할까?

앞에서 말했듯 첫 번째 숫자를 고정했을 때 나올 수 있는 순열의 개수는 6이다. 그러면 3 ≤ 6 이기 때문에 첫 번째 숫자는 1이 된다.

그리고 두 번째 숫자를 고정했을 때의 경우의 수는 2로, 3보다 작다. 따라서 두 번째 자리에 올 수 있는 수는 다음 수인 3으로 넘어가게 된다. 그러면 지금 1 2 _ _ 를 지나 1 3 _ _ 인 경우를 보고 있기 때문에 총 가능한 경우의 수는 2! * 2 = 4가 된다. k ≤ 4 로 1 3 _ _ 안에 k번째 순열이 존재하게 된다.

지금 1 2 _ _ 인 경우를 모두 지나왔으니 k에서 1 2 _ _ 인 경우를 모두 빼주어야 한다. 다시 말해서 첫 번째 순열(1 2 3 4)와 두 번째 순열(1 2 4 3)은 찾은 셈이니 남은 경우의 수만 구하면 되는 것이다.

이런 식으로 첫 번째 자리부터 N번째 자리까지 반복하면 k번째 순열을 구할 수 있다.

2. 몇 번째 순열인지 찾기

입력된 순열의 첫 번째부터 N번째 자리까지 돌면서 현재 자리의 숫자가 몇 번째 숫자인지 확인한다. 그리고 현재 자리 바로 뒷 자리 순열의 경우의 수 * 숫자의 순서 를 곱한 다음 정답 변수에 이 값을 더해준다.

1번을 이해하면 2번의 풀이방법 역시 쉽게 이해할 수 있다.