[Swift] 백준_암호 만들기(1759)

문제

 

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

1759번: 암호 만들기

 

 

풀이

 

간단한 백트래킹 문제였다.

 

모든 경우를 찾아준 뒤에 암호의 길이와 동일한 배열이 완성되면, 조건을 만족하는지 확인해주었다.

 

나는 아래처럼 해결했지만 자음을 굳이 선언하지 않고 vowel에 포함되는지 확인하여 자음과 모음을 분리할 수 있을 것이다. 이렇게하면 메모리를 조금이나마 줄일 수 있을 것 같다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let l = input[0]; let c = input[1]
let vowel = ["a","e","i","o","u"]
let con = ["b","c","d","f","g","h","j","k","l","m","n","p","q","r","s","t","v","w","x","y","z"]
let list = readLine()!.split(separator: " ").map { String($0) }.sorted(by: <)
var result: [[String]] = []
func dfs(_ arr: [String], _ idx: Int) {
    if arr.count == l {
        if arr.filter { vowel.contains($0) }.count < 1 {
            return
        }
        if arr.filter { con.contains($0) }.count < 2 {
            return
        }
        print(arr.joined())
        return
    }
    for i in idx..<list.count {
        dfs(arr + [list[i]], i + 1)
    }
}
dfs([],0)

 

 

_____________________________________________________________________________________________________

 

백트래킹 문제는 난이도 차이가 심한듯