코딩테스트 연습 - 스킬트리

문제 풀이 아이디어

일단 문제를 읽자마자 편안한 것이 String인 skill의 길이는 최대 26, Array인 skill_trees의 길이는 최대 20에 불과합니다. 시간 초과에 대한 걱정 없이 원하는 대로 구현하면 되는 것이죠.

Swift에서 문자열을 다루는 것은 파이썬 같은 언어에 비해서는 살짝 복잡하고 비용도 더 높은 작업입니다. N이 크다면 상당히 신경써서 해야하는 작업입니다.

코드

1. 모든 가능한 Case를 구해놓는 방법

첫 번째로 제가 푼 방식은 주어진 skill을 가지고 가능한 모든 Case를 구해놓고 푸는 방식입니다. 예를 들어 skill이 “BCD”라면 B, C, D 스킬을 찍는 모든 경우의 수는 "", "C", "CB", "CBD" 가 됩니다.

이렇게 모든 Case를 구해놓고 나서 skill_trees에 있는 스킬 트리에서 B, C, D를 제외한 모든 스킬을 제거한 결과가 모든 Case 안에 포함되어 있는지 확인하는 방법입니다.

이 과정에서 String.Index를 활용했습니다.

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    
    var count = 0
    var possible_case = [String]()
    
    // 가능한 모든 case 미리 구하기
    for i in 0...skill.count {
        let fromIndex = skill.index(skill.startIndex, offsetBy: 0)
        let toIndex = skill.index(skill.startIndex, offsetBy: i)
        possible_case.append(String(skill[fromIndex..<toIndex]))
    }
    
    // tree에서 순서가 정해진 skill을 제외한 결과가 가능한 모든 case와 동일한지 확인
    for tree in skill_trees {
        var tree = tree
        tree.removeAll { !skill.contains($0) }
        if possible_case.contains(tree) { count += 1 }
    }
    
    return count
}

2. prefix를 활용하는 방법

String의 메소드인 prefix(n)는 최초의 n의 길이 만큼만 String을 반환합니다. 이 방법을 활용하면 위에 String.Index를 사용한 방법보다 더 간단하게 풀 수 있습니다.

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    var count = 0
    
    for tree in skill_trees {
        let tree = tree.filter { skill.contains($0) }
        if skill.prefix(tree.count) == tree { count += 1 }
    }
    
    return count
}