2021년 1월 24일 JavaScript 코드를 추가했습니다.
문제
선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.
예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일 때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.
위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.
선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
입력
- 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
- 스킬 순서와 스킬트리는 문자열로 표기합니다. 예를 들어,
C → B → D라면 CBD로 표기합니다. - 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
- skill_trees는 길이 1 이상 20 이하인 배열입니다.
- skill_trees의 원소는 스킬을 나타내는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.
출력
첫째 줄에 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.
예제 입력
| skill | skill_trees |
|---|---|
| "CBD" | ["BACDE", "CBADF", "AECB", "BDA"] |
예제 출력
2풀이에 사용할 알고리즘 구상
스킬을 배우는 순서가 정해져 있고, 이 순서를 지켜야 한다는 제약조건을 보고 바로 스택 자료구조를 사용해야겠다고 생각했다. 다만 이 문제를 까다롭게 만드는 요소는, skill(이하 "선행 스킬 순서")에 없는 스킬은 스킬트리가 어떻든 상관 없이 아무때나 배울 수 있다는 점이다. 따라서, skill_trees의 원소(이하 "입력으로 주어지는 스킬트리")에서 선행 스킬 순서에 있는 스킬에 한하여 순서를 어겼는지 확인해야 한다.
다행히 선행 스킬 순서는 하나만 주어지기 때문에, 입력으로 주어지는 스킬트리의 스킬들을 분석하여 해당 스킬이 선행 스킬 순서에 포함되어 있는지 아닌지를 확인하는 함수가 필요하다고 생각하여 isSkill()이라는 함수를 하나 만들었다. 이 함수는 입력으로 주어지는 스킬트리에서 스킬을 하나씩 인자로 받아 이 스킬이 선행 스킬 순서에 있는지 없는지를 확인한다.
입력으로 주어지는 스킬트리에서 각 스킬에 대해 확인 과정을 거친 결과 해당 스킬이 선행 스킬 순서에 없다면, 해당 스킬에 대해서는 신경쓰지 않도록 한다. 만약 그렇지 않다면, 해당 스킬이 선행 스킬 순서를 어기고 있는지 확인해야 한다. 이 역할을 해주는 함수 val()을 만들었다.
그렇다면 그 확인 과정은 어떻게 진행될까? 입력으로 주어지는 스킬트리를 앞에서부터 읽는다고 가정하면, 선행 스킬 순서를 뒤집어서 스택에 넣어둔다. 그리고 입력으로 주어지는 스킬트리를 앞에서부터 차례로 읽다가, 이 스택에 있는 원소와 스택의 가장 위에 있는 원소 top()가 같을 경우 pop()을 진행한다. 만약에 다를 경우, 이 스킬트리는 불가능한 스킬트리다. 입력으로 주어지는 스킬트리의 끝까지 읽었음에도 다른 경우가 한 번도 없어야 가능한 스킬트리다. 왜 이런지 지금부터 천천히 설명하도록 하겠다.
위 그림은 문제에서 예제로 주어졌던 불가능한 스킬트리다. 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더이므로 스택에는 뒤집어서 썬더 → 라이트닝 볼트 → 스파크의 순서로 넣는다. 스택은 먼저 넣은 것이 가장 안에 있기 때문에 스택의 가장 위에는 스파크가 있다. 이 때 입력으로 주어지는 스킬트리(여기서는 라이트닝 볼트 → 스파크 → 힐링 → 썬더) 를 앞에서부터 읽어보자. 읽기 시작하자마자 오류가 발생한다. 첫 번째 스킬 라이트닝 볼트는 분명히 선행 스킬 순서(스택)에 있는 스킬인데, 스택의 가장 위에는 스파크가 있다. 둘이 다르기 때문에 이 경우는 무조건 불가능한 스킬트리다.
위 그림은 문제에서 예제로 주어졌던 가능한 스킬트리다. 선행 스킬 순서와 스택은 위의 경우와 동일하다. 이 때 입력으로 주어지는 스킬트리(여기서는 스파크 → 힐링 → 라이트닝 볼트 → 썬더)를 앞에서부터 읽어보자. 첫 번째 스킬 스파크가 스택에 있는 스킬이기 때문에 스택의 가장 위에 있는 스킬과 비교한다. 둘이 같으므로 스택에서 pop()을 진행한다. 두 번째 스킬 힐링은 스택에 없는 스킬이기 때문에 그냥 넘어간다. 세 번째 스킬 라이트닝 볼트는 스택에 있는 스킬이기 때문에 스택의 가장 위에 있는 스킬과 비교한다. 둘이 같으므로 스택에서 pop()을 진행한다. 이와 같은 방식으로 스킬트리의 끝까지 비교를 진행했을 때까지 오류가 발생하지 않으면 이 스킬트리는 가능한 스킬트리다.
이 과정을 진행해주는 코드를 작성하면 된다.
제출 코드
#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
// 스킬이 선행 스킬 순서에 있는지 확인하는 함수
bool isSkill(string skill, char a){
for (int i = 0; i < skill.size(); i++){
if (a == skill[i]) return true;
}
return false;
}
// 스킬트리가 가능한 스킬트리인지 확인하는 함수
bool val(string skill, string indv, stack<char> temp){
bool answer = true;
for (int i = 0; i < indv.size(); i++){
// 스킬이 스택에 있는 스킬인지 확인한다.
if (isSkill(skill, indv[i])){
// 스택의 top()과 다르면 false를 반환한다.
if (indv[i] != temp.top()){
answer *= false;
}
// 스택의 top()과 같으면 스택을 pop()한다.
else {
temp.pop();
}
}
}
return answer;
}
int solution(string skill, vector<string> skill_trees) {
int answer = 0;
string strtmp = "";
stack<char> temp;
for (int i = skill.size()-1; i >= 0; i--){
temp.push(skill[i]);
}
for (int i = 0; i < skill_trees.size(); i++){
if (val(skill, skill_trees[i], temp)) answer++;
}
return answer;
}function inSkillTree(skill, skillList) {
return skillList.indexOf(skill) === -1 ? false : true;
}
function validate(skillTree, condition) {
condition = condition.slice();
for (let eachSkill of skillTree) {
if (inSkillTree(eachSkill, condition)) {
if (eachSkill !== condition[0]) return false;
else condition.shift();
}
}
return true;
}
function solution(skill, skill_trees) {
let answer = 0;
let condition = skill.split("");
skill_trees.forEach(eachTree => {
if (validate(eachTree, condition)) answer++;
});
return answer;
}
회고
나는 문제를 풀 때 스택을 사용했지만 다른 사람들은 대부분 스택을 사용하지 않고 푼 것 같다. 배열만으로도 푼 사람이 있었고, 해쉬 맵을 사용하여 푼 사람도 있었다. 그리고 나는 스킬트리를 뒤집어서 스택에 넣어서 문제를 풀었는데, 그냥 순서대로 큐에 넣어서 문제를 풀어도 된다. 사실 이게 더 쉽고 간단하다... 왜 이 생각을 못 했는지 아직도 모르겠다. 괜히 어렵게 푼 것 같다. 그리고 C++ 대신 자바스크립트를 사용해서 푼 코드도 봤는데 역시 배열 처리에는 자바스크립트가 더 짧고 강력하다는 사실을 다시금 깨달은 순간이었다. 아래 링크에서 전부 확인해 보자.
참고하면 좋은 링크
짧고 강력하게 푸는 방법
Queue를 사용하여 푸는 방법
Hash map을 사용하여 푸는 방법
배열을 만들어서 푸는 방법
