[Swift] 프로그래머스 연습 문제(Level 2) : 스킬트리

실제 코딩테스트의 문제를 통하여 알고리즘 분석과 코딩 능력을 향상시킵니다.

 

 

#. 구독 대상

• 기본 알고리즘을 코딩 테스트 문제를 통하여 학습하고 싶으신 분
• 취업 및 이직을 준비하고 계신 개발자
• Swift를 통하여 코딩 테스트 문제를 살펴보고 이해를 하고 싶으신 분
• 코딩 테스트에 대한 거부감을 없애기 위하여 기초부터 하나씩 공부해보고 싶으신 분
• 기타 알고리즘과 문제 해결 능력에 대해서 관심이 있는 모든 개발자분

참고 사항

본 코딩 테스트 문제에 대한 설명 및 해결 방안은 최적의 답이 아닐 수 있습니다.

본 강의에서 지향하는 목표는 바로 특정 문제에 대한 최적의 해결 방법을 찾기보다는 특정한 문제에 대해서 충분히 이해할 수 있고 다양한 방법을 통하여 해결하는 방법을 찾고 향상시키는데 그 목적이 있습니다.

좀 더 좋은 알고리즘 및 코드가 있으시다면 언제든지 본 게시물의 댓글을 통해서 제시해주시면 감사하겠습니다.

 

 

 

---

 

 

 

코딩 테스트 문제

 

먼저 오늘 살펴볼 문제에 대해서 먼저 살펴보겠습니다.

 

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

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

 

 

 

 

---

 

 

 

문제 설명

 

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

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

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

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

 

 

 

 

---

 

 

 

제한 조건

 

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

 

 

 

 

---

 

 

 

 

입출력 예

skill	skill_tree	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

 

 

 

 

---

 

 

문제 분석

 

오늘 문제는 게임에서의 스킬 트리와 관련된 조금 특별한 문제입니다. 문자열로 구성된 선행 스킬 트리가 주어지며 유저가 만든 특정 스킬 트리 리스트에서 서로 비교하여 유저가 만든 스킬 트리가 주어진 선행 스킬 트리 기준으로 가능한 스킬 트리의 갯수가 몇 개인지 찾아서 최종 반환하면 되는 문제입니다.

 

 

 

 

 

---

 

 

 

알고리즘

 

그렇다면 본 문제를 해결하기 위한 알고리즘을 하나씩 살펴보면 아래와 같습니다.

 

 

• 가능한 스킬트리의 가능 여부의 개수를 반환할 변수를 선언한다.
• 유저 스킬 리스트에 대해 반복하면서 하나씩 스킬 문자열을 추출한다.
• 주어진 유저 스킬 트리에서 비교할 스킬(선행 스킬) 문자열에 있는 문자만 추출할 대상 문자열을 선언한다.
• 유저 스킬 트리의 문자열을 하나씩 문자 단위로 비교한다.
• 현재 유저 스킬 트리의 특정 문자가 선행 스킬 문자열에 있는 문자인지 체크한다.
• 현재 특정 문자가 선행 스킬 문자열에 있는 문자라면 최종 비교할 대상 문자열에 현재 문자열을 추가한다.
• 최종 선행 스킬 문자열을 시작 문자 기준으로 대상 스킬 문자열을 포함하여 시작하고 있다면 스킬 가능 카운트를 증가시킨다.
• 최종 스킬 가능 카운트를 반환한다.

 

 

 

 

---

 

 

 

코드 설명

 

그렇다면 위의 알고리즘에 대해서 하나씩 살펴보면서 코드로 작성을 해보도록 하겠습니다.

 

 

• 가능한 스킬트리의 가능 여부의 개수를 반환할 변수를 선언한다.

var count = 0

 

• 유저 스킬 리스트에 대해 반복하면서 하나씩 스킬 문자열을 추출한다.

for tree in skill_trees {

}

 

• 주어진 유저 스킬 트리에서 비교할 스킬(선행 스킬) 문자열에 있는 문자만 추출할 대상 문자열을 선언한다.

var targetSkill = ""

 

• 유저 스킬 트리의 문자열을 하나씩 문자 단위로 비교한다.

for s in tree {

}

 

• 현재 유저 스킬 트리의 특정 문자가 선행 스킬 문자열에 있는 문자인지 체크한다.
• 현재 특정 문자가 선행 스킬 문자열에 있는 문자라면 최종 비교할 대상 문자열에 현재 문자열을 추가한다.

for s in tree {
    if skill.contains(s) {
        targetSkill += String(s)
    }
}

 

• 최종 선행 스킬 문자열을 시작 문자 기준으로 대상 스킬 문자열을 포함하여 시작하고 있다면 스킬 가능 카운트를 증가시킨다.

if skill.hasPrefix(targetSkill) {
    count += 1
}

 

• 최종 스킬 가능 카운트를 반환한다.

return count

 

 

 

 

 

 

 

위의 코드들을 모두 조합하여 최종 코드를 완성하면 아래와 같습니다.

 

 

최종 코드

import Foundation

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    // 가능한 스킬트리의 가능 여부의 개수를 반환할 변수를 선언한다.
    var count = 0
    
    // 유저 스킬 리스트에 대해 반복하면서 하나씩 스킬 문자열을 추출한다.
    for tree in skill_trees {
        // 주어진 유저 스킬 트리에서 비교할 스킬(선행 스킬) 문자열에 있는 문자만 추출할 대상 문자열을 선언한다.
        var targetSkill = ""
        
        // 유저 스킬 트리의 문자열을 하나씩 문자 단위로 비교한다.
        for s in tree {
            // 현재 유저 스킬 트리의 특정 문자가 선행 스킬 문자열에 있는 문자인지 체크한다.
            if skill.contains(s) {
                // 현재 특정 문자가 선행 스킬 문자열에 있는 문자라면 최종 비교할 대상 문자열에 현재 문자열을 추가한다.
                targetSkill += String(s)
            }
        }
        
        // 최종 선행 스킬 문자열을 시작 문자 기준으로 대상 스킬 문자열을 포함하여 시작하고 있다면 스킬 가능 카운트를 증가시킨다.
        if skill.hasPrefix(targetSkill) {
            count += 1
        }
    }
    
    // 최종 스킬 가능 카운트를 반환한다.
    return count
}

 

 

 

 

 

---

 

 

 

이상으로 오늘 제시한 문제에 대해서 분석 및 코드를 작성해 보았습니다.

 

감사합니다.

 

 

 

 

---

[참고 자료(References)]

 

 

[1] 프로그래머스 - 스킬트리 : https://programmers.co.kr/learn/courses/30/lessons/49993