스킬트리

LEEHAKJIN-VV·2022년 6월 20일
0

프로그래머스

목록 보기
31/37

출처: 프로그래머스 코딩 테스트 연습

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한 사항

  • 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

  • 스킬 순서와 스킬트리는 문자열로 표기합니다.

    • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
  • 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.

  • skill_trees는 길이 1 이상 20 이하인 배열입니다.

  • skill_trees의 원소는 스킬을 나타내는 문자열입니다.

    • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

skillskill_treesreturn
"CBD"["BACDE", "CBADF", "AECB", "BDA"]2

입출력 예 설명

  • "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.

  • "CBADF": 가능한 스킬트리입니다.

  • "AECB": 가능한 스킬트리입니다.

  • "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

내가 제출한 코드

import Foundation

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    var answer: Int = 0  
    let existSkill = skill_trees.map{ // 선행 스킬이 아닌 스킬 제거
        $0.filter{skill.contains($0)}
    }
    
    /*
    1. skill_tree가 skill에 포함된다면 스킬 트리 순서를 지킴
    2. skill_tree의 첫문자는 무조건 입력으로 들어온 skill의 첫문자여야한다.
    3. skill_tree이 빈 문자열인 경우 스킬트리에 우선순위가 상관 없는 문자열이 들어온 경우
    */
    for skill_tree in existSkill {
        if skill.contains(skill_tree) && skill_tree.prefix(1) == skill.prefix(1) 
        || skill_tree.isEmpty {
            answer += 1
        }
    }
    return answer
}

코드 설명

문제는 단순 구현 문제이다. 특별한 알고리즘을 요구하지 않는다. 그러나 스킬 트리의 순서를 비교하는 방법에 따라 구현 난이도가 다르다. 이번 풀이에서 스킬 트리의 순서를 비교하기 위해 사용한 로직은 skill_trees에서 선행 스킬 순서가 존재하지 않는 스킬은 제거이다. 이유는 코드를 설명할 때 다룬다.

그러면 코드를 살펴보자.

앞에서 언급했듯이, 스킬 트리에서 선행 스킬이 정해지지 않는 스킬을 제거하는 코드다.

var answer: Int = 0  
    let existSkill = skill_trees.map{ // 선행 스킬이 아닌 스킬 제거
        $0.filter{skill.contains($0)}
    }
// skill_trees: ["BACDE", "CBADF", "AECB", "BDA"]
// Prints existSkill: ["BCD", "CBD", "CB", "BD"]

제거를 한 이유는 문제를 살펴보면 선행 스킬 순서에 없는 다른 스킬은 순서에 상관없이 배울 수 있다.라는 문구가 존재한다. 즉 순서를 비교하기 위해 다른 스킬은 불필요하므로 이를 제거하는 것이다. 제거하는 방법은 클로저를 이용한다.

이제 선행 스킬의 순서를 지키는지 확인을 할 차례다.

 for skill_tree in existSkill {
        if skill.contains(skill_tree) && skill_tree.prefix(1) == skill.prefix(1) 
        || skill_tree.isEmpty {
            answer += 1
        }
    }

여기서 우리가 굳이 노력을 들여 입력으로 들어온 스킬 트리(skill_trees)에서 굳이 선행 스킬 정보가 없는 스킬을 제거한 이유를 알 수 있다. 우리는 제거되고 남은 스킬 트리existSkill이 가능한 스킬 트리 인지 판별하기 위해 3가지 방법을 사용한다.

  1. contains 메소드를 이용한 방법

  2. 판별하려는 스킬트리의 첫 스킬 비교

  3. 판별하려는 스킬트리가 비었는지 확인

각 방법에 대해 자세히 설명을 해보면, 선행 스킬의 순서가 A->B->C 라면 BA와 같이 스킬의 순서가 바뀌면 해당 스킬트리는 불가능하다. 이를 판별할 수 있는 방법이 contains 메소드이다. 이 메소드는 호출하는 문자열에 파라미터로 들어온 문자열을 포함하는지 확인하는 메소드이다. 이를 이용하면 "ABC".contains("BA") => false와 같이 순서가 뒤바뀐 경우를 판별할 수 있다.

다음으로 첫 문자를 비교하는 이유를 설명한다. 우리는 선행 스킬 순서가 없는 스킬을 모두 제거하였다. 만약 제거하고 남은 스킬들이 배열의 원소에 존재한다면 그 배열의 문자열의 첫 문자는 반드시 skill의 첫 문자와 같을 것이다. 만약 다르다면 이는 어떠한 한 스킬이 제일 우선순위가 높은 스킬을 배우지 않고 배웠다는 뜻이다.

마지막으로 빈 문자열을 확인하는 이유는 예를 보면서 이해하자. 선행 스킬 순서가 "CBD"이라고 가정하고, 이를 이용하여 스킬 트리 "EFGH"가 배울 수 있는지 판별하자. 코드의 처음에서 우리는 선행 스킬이 아닌 스킬을 모두 제거하였으므로 해당 스킬 트리는 판별을 하는 순간 빈 문자열이 된다. 그러나 우리는 "EFGH"에 각 스킬은 순서에 상관없이 배울 수 있으므로 스킬트리로 가능하다는 것을 알고 있다. 그렇기 때문에 skill_tree이 빈 문자열인 경우는 판별하려는 스킬들의 선행 순서가 존재하지 않으므로 스킬 트리로 만들 수 있다는 결론을 얻을 수 있다.

위 3가지 경우 중 1번과 2번을 동시에 만족하거나, 3번을 만족하면 가능한 스킬 트리라고 판별을 하면 된다.

0개의 댓글