Programmers) Lv2 스킬트리

출처: https://programmers.co.kr/learn/courses/30/lessons/49993

분류: Lv2

---

접근방식

선행 스킬에 없는 스킬은 무시하면 되고 선행 스킬의 스킬을 순서대로 배우는지 확인하면 되는 문제입니다.

해당 키값(스킬)에 빠르게 접근할 수 있는 자료구조가 필요하다고 생각했고 해시를 떠올렸습니다.

 

해결방법

따라서 가장 먼저 배워야 하는 선행 스킬만 true 나머지는 false로 해서 Dictionary로 만들었습니다.

그 후 true인 스킬을 확인하고 나면 그 다음 선행 스킬을 true로 만들어줍니다.

선행 스킬이 모두 true가 되면 그 스킬 트리는 배울 수 있으므로 카운팅해주고 넘어갑니다.

당연히 선행 스킬에 없는 스킬은 nil 값이므로 넘어가면됩니다.

func solution(_ skill:String, _ skill_trees:[String]) -> Int {

    var skillChecker = [Character: Bool]()
    var resultCnt = 0

    for s in skill { skillChecker[s] = false }
    let startChecker = skillChecker

    for checkedSkill in skill_trees {

        // 초기화
        skillChecker = startChecker
        skillChecker[skill.first!] = true
        var index = 1
        var isPass = true

        for skillChar in checkedSkill {

            if index == skill.count { break }

            if let isAccess = skillChecker[skillChar] {
                if isAccess {
                    let idx = skill.index(skill.startIndex, offsetBy: index)
                    skillChecker[skill[idx]] = true
                    index += 1
                } else {
                    isPass = false
                    break
                }
            }
        }

        if isPass {
            resultCnt += 1
        }
    }


    return resultCnt
}

 

# 다른 풀이

true 인 스킬을 확인하고 다음 선행 스킬을 true로 만들어주려면 index를 만들어 체크해줘야 하는데,

dic는 nil 유무를 판단하는 데만 사용하고

대신 stack으로 만들어 stack의 top과 비교해가면서 풀 수도 있겠습니다.

 

# 다른 풀이

제 뒤통수를 땅~ 하고 때렸던 풀이 입니다.

이 문제의 핵심은 해당 원소 체크, 순서 체크 입니다.

따라서 dictionary를 만들어 일일이 확인하는 대신 해당하는 원소는 걸러줍니다.

이제 해당하는 원소만 남아있고 그 순서만 확인하면 되므로 시퀀스의 순서를 확인하는 starts(with:) 자료구조를 사용합니다.

이렇게 하면 몇 줄만으로 해결이 되더군요... 👍

func solution(_ skill:String, _ skill_trees:[String]) -> Int {

    func available(_ s: String, _ t: String) -> Bool {
        let alza = t.filter { s.contains($0) }
        return s.starts(with: alza)
    }

    return skill_trees.map { available(skill, $0) }.filter { $0 }.count
}

/** 송치원님 풀이입니다. **/

 

배운점

원소 체크 필터링 방법,

확인대상.filter {  포함될원소들.contains($0) }

 

starts(with:) : 해당 시퀀스들의 시작이 일치하는지 확인한다.

let 확인대상들 = ["BCD", "CBD", "CB", "BD"]

let 예상결과 = "CBD"

for 확인대상 in 확인대상들 {
    let result = 예상결과.starts(with: 확인대상)
    
    print("\(확인대상): \(result)")
    /*
    BCD: false
    CBD: true
    CB: true
    BD: false
    */
}

 

오답원인

 

회고

문제를 어떻게 풀어야 할 지 접근하고 생각하는 것도 중요하지만

그걸 어떻게 구현할 지도 중요하다.

문제를 푸는 것 자체도 중요하지만 

효율적으로 푸는 것도 중요하다.

연습 또 연습만이 살 길 🤜