dfs?_백준_1759

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

 

문제 접근

1. 입력받은 alphabets를 오름차순으로 sort. 이는 순차적으로 큰 알파벳을 넣기 위함.
2. 각 알파벳에 대하여 재귀를 실행.
3. 재귀 내부 : 실행 상태의 start의 마지막 알파벳보다 큰 알파벳이 있는지 inputAlphabets 내부를 검사 및 첫번째 인덱스 저장.
4. 다음 start에 찾은 인덱스의 알파벳을 추가하고, 현재 inputAlphabets에서 인덱스이하의 값을 제외하고 다음 inputAlphabets에 전달
5. 자음과 모음 조건 여부 : L 조건을 만족한 단어에서 모음을 전부 제거했을 때, 2보다 크다면 자음이 2개 이상있는 것이며, 지우기 전의 count보다 작아진다면, 모음이 삭제된 것으로, 모음이 1개 이상 있다고 판단 할 수 있다.

 

실수했던 점 

• 정답을 출력하는 방법이 틀렸었음 

  • print(answerList) // 틀린 코드
    
    for answer in asnwerList { // 이와 같이 수정
    	print(answer)
        }

• func isSatisfied의 return 조건이 유연하지 못했음.

  •     func isSatisfied(_ with : String) -> Bool {
            var target = with
            
            ...
            
            
            return count ==2 || count == 3 // 의 코드에서
            return count >= 2 && count <= with.count - 1 // 로 수정됨
        }

정답 코드

import Foundation

let settings = readLine()!.components(separatedBy: " ")
let alphabets = readLine()!.components(separatedBy: " ")

let countLimit = Int(settings[0])!
let vowels: [Character] = ["a", "e", "i", "o", "u"]

func start() {
	var answerList: [String] = []
    let sortedAlphabets = alphabets.sorted(by: <)
        
    for nextAlphabet in sortedAlphabets {
    	let tempAlphabets = sortedAlphabets.filter({
        	$0 != nextAlphabet
		})
            
		let result = recursion(start: nextAlphabet, limit: countLimit, inputAlphabets: tempAlphabets)
		answerList += result
    }
    
    for answer in answerList {
        print(answer)
    }
}


func isSatisfied(_ with : String) -> Bool {
    var target = with

    for vowel in vowels {
        guard let idx = target.firstIndex(of: vowel) else {
            continue
        }
        target.remove(at: idx)
    }

    let count = target.count

    return count >= 2 && count <= with.count - 1
}
    
func recursion(start: String, limit:Int, inputAlphabets: [String]) -> [String] {
        var sol: [String] = []
    
        if start.count == limit && isSatisfied(start) {
            sol.append(start)
            return sol
        }
        
        guard let idx = inputAlphabets.firstIndex(where: {
            $0 > String(start.last!)
        }) else {
            return sol
        }
        
        let nextAlphabets = Array(inputAlphabets[idx...inputAlphabets.endIndex - 1])
        
        for next in nextAlphabets {
            let newStart = start + next
            sol.append(contentsOf: recursion(start: newStart, limit: limit, inputAlphabets: nextAlphabets))
        }
        
        return sol
}

start()