12980좋아하는 수열 - swift

https://www.acmicpc.net/problem/12980

흠..이 문제는 풀이가 없는 것 같아서 내가 먼저 올린다. 그래야 조회슈 ㅎ...는 농담이고 문제가 재밌다.

문제분석

1. 순열의 크기 n이 주어진다. 그리고 1..N까지 써야하는 배열이 있다.  이 배열에는 0이 있는데 이는 지워졌다는 것을 의미한다.

2. 즉 0자리에는 이미 배열에 있는 수 말고 1..N까지의 수 중 아무거나 사용할 수 있다.

3. 하지만 S 점수를 맞추는 경우의 수를 구해야한다.

4. 점수? [1,2,3] 이라고 보면 [1,2] , [1,3], [2,3]의 케이스가 가능하기에 총 3점이다. 이런식으로 배열의 인덱스와 값을 비교해  i < j이면서 S[i] < S[j]의 쌍의 개수이다.

문제접근

1. 0인 곳에 남은 수로 채워서 모든 경우를 구해보자.2. 그 케이스별로 계산을 하여 합이 S가 되는 경우가 있으면 정답+=1해주면 되겟다.3. 하지만 시간 효율을 위해 백트래킹을 적용하여 0을 이미 다 채웠을때 더 이상은 돌지 않도록 리턴해주었다. 또한 그 때 계산하여 합이 S면 정답 += 1해주었다.

코드

import Foundation
let ns = readLine()!.split(separator: " ").map{Int(String($0))!}, n = ns[0], s = ns[1]
let arrs = readLine()!.split(separator: " ").map{Int(String($0))!}

func countPermutationsWithScore(n: Int, s: Int, initialArray: [Int]) -> Int {
    var possibleValues = Set(1...n)
    var zeroinDices = [Int]()
    for value in initialArray where value != 0 {
        possibleValues.remove(value)
    }
    for (index, value ) in initialArray.enumerated() where value == 0 {
        zeroinDices.append(index)
    }
    let possibleArray = Array(possibleValues)

    var cnt = 0
    func calculateScore(_ array: [Int]) -> Int {
        var score = 0
        for i in 0..<array.count {
            for j in (i+1)..<array.count {
                if array[i] < array[j] {
                    score += 1
                }
            }
        }
        return score
    }
    // 0인 곳에 하나씩 채워보자.
    func backTracking(_ index: Int, _ currentAraay: [Int], _ usedNums: Set<Int>) {
        if index == zeroinDices.count {
            if calculateScore(currentAraay) == s {
                cnt += 1
            }
            return
        }
        let position = zeroinDices[index]
        for value in possibleArray {
            if usedNums.contains(value){
                continue
            }
            var newArr = currentAraay
            newArr[position] = value
            var newUsedNums  = usedNums
            newUsedNums.insert(value)
            backTracking(index + 1 , newArr, newUsedNums)
        }
    }
    let initialUsedNumbers = Set(initialArray.filter { $0 != 0 })
    backTracking(0, initialArray,initialUsedNumbers)
    return cnt
}
print(countPermutationsWithScore(n: n, s: s, initialArray: arrs))

먼저 n이 들어왔을때 1..n까지의 값

이 가능하기에 그 중 이미 사용된 값을 제거해준다. 그러면 실제 0인 곳에 넣을 수 있는 배열을 만든다.

그 후 두번째줄에 온 배열중에 어디가 0인지를 알기 위해 zeroindices를 만들어 인덱스를 저장한다.

그 후 백트래킹으로 0인 곳에 가능한숫자 하나씩 넣어보며 경우를 구해주는 방식이다.

안타깝게도 다른 풀이가 없다 헷 첨이다. 원조 맛집을 외칠 수 있다.