백준 1759 암호만들기

출처: https://www.acmicpc.net/problem/1759

분류: 백트래킹

---

접근방식

백트래킹 방식으로 풀어봤습니다.

완성한 암호가 모음 1개 자음 2개 이상인지 확인해야 하는 것만 주의하면 어렵지 않게 풀 수 있을 것 같네요!

체크하는 건 모음 set을 만들어두고 완성된 문자열과 교집합을 구해서 카운트하는 방식으로 풀어봤습니다 :)

 

해결방법

let lc = readLine()!.split(separator: " ").map { Int($0)! }
var alphabets = readLine()!.split(separator: " ").sorted()
var available = [Bool](repeating: true, count: lc[1])
var predicted: String = ""
var vowel = Set<Character>("aeiou")

func makeDecryption(idx: Int) {
    guard predicted.count != lc[0] else {
        let countOfVowel = vowel.intersection(predicted).count
        if countOfVowel >= 1, predicted.count - countOfVowel >= 2 {
            print(predicted)
        }
        return
    }
    
    for i in idx..<alphabets.count where available[i] {
        available[i] = false
        predicted.append(contentsOf: alphabets[i])
        makeDecryption(idx: i+1)
        available[i] = true
        predicted.popLast()
    }
}

makeDecryption(idx: 0)

 

배운점

또 모음 1개 자음 2개를 빼먹어서 틀렸다. 문제를 잘 읽자 !!