[programmers/Swift] 스킬트리

programmers.co.kr - 코딩테스트연습 - Lv.2 - Summer/Winter Coding (~2018) - 스킬트리

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

Constraints :

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/06/01.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    return skill_trees.filter { tree in
        var queue = skill.map { $0 }
        for skill in tree {
            if queue.contains(skill) {
                if let first = queue.first, first == skill {
                    queue.removeFirst()
                } else {
                    return false
                }
            }
        }
        return true
    }.count
}

print(solution("CBD", ["BACDE", "CBADF", "AECB", "BDA"])) // 2

How I tried this :
각 skill_tree를 돌며 올바른 스킬순서인가 확인해서 

올바른 스킬순서인 갯수를 카운트

 

스킬이 포함되어 있지 않으면 관련없는 스킬이므로 건너 뛰고,

해당 스킬이 포함되어 있는데 현재 dequeue 된 스킬과 다르면 순서가 어긋난 스킬

해당 스킬이 포함되어 있고 현재 dequeue 된 스킬과 같으면 순서가 올바름

 

모든 스킬이 queue 스킬과 순서가 올바르게 끝나면 true로 filter

중간에 어긋나면 false로 필터제거

문제에 관한 모든 저작권 : https://programmers.co.kr/