어제 푼 알고리즘이 구현 문제였는데 너무 어려웠어서..이번에도 구현 문제를 했다. 조금 더 낮은 난이도로!

구현 알고리즘

• 구현 알고리즘이란?
  머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 거의 모든 문제가 '구현 문제'인데 구현이 어려운 문제들이 있다. 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다.
  구현 문제는 모든 범위의 문제 유형을 포함하고 프로그래밍 언어의 문법과 라이브러리를 잘 알고 있어야 풀 수 있다.

생각흐름

unordered_map에 각 스킬과 순서를 저장해 주었고 BOOL배열로 스킬을 배웠는지 여부를 저장하였다.
skill_trees에서 스킬을 하나씩 확인하면서 해당 스킬이 주어진 스킬에 포함되어 있는지 확인하고 해당 스킬의 선행 스킬을 모두 배웠는지 BOOL배열을 통해 확인해 주었다. 만약 선행 스킬을 배우지 않았다면 Check = false로 해주었고 모든 스킬을 다 돌고 나서 순서대로 스킬을 배웠다면 answer++을 해주었다.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(string skill, vector<string> skill_trees){
    int answer = 0;
    // 각 스킬의 인덱스를 저장할 unordered_map을 생성
    unordered_map<char,int> m;
    for(int i=0;i<skill.length();i++){
        // 각 스킬과 해당 스킬의 인덱스를 unordered_map에 삽입
        m.insert({skill[i],i});
    }
    
    for(int i=0;i<skill_trees.size();i++){
        // 스킬을 배웠는지 여부를 저장하는 배열을 생성
        vector<bool> BOOL(skill.length());
        // 해당 스킬트리가 가능한지 여부를 저장하는 변수를 생성
        bool Check = true;
        for(int j = 0;j<skill_trees[i].length();j++){
            // 각 스킬트리에서 스킬을 하나씩 확인
            char c = skill_trees[i][j];
            // 해당 스킬이 주어진 스킬에 포함되어 있는지 확인
            if(m.find(c)!=m.end()){
                // 해당 스킬의 선행 스킬을 모두 배웠는지 확인
                if(m[c] == 0){
                    BOOL[0] = true;
                } else{
                    if(BOOL[m[c]-1] == true){
                        BOOL[m[c]] = true;
                    } else{
                        // 선행 스킬을 배우지 않았다면 해당 스킬트리는 불가능
                        Check = false;
                        break;
                    }
                }
            }
        }
        // 스킬트리가 가능하다면 answer을 증가
        if(Check) answer++;
    }

    return answer;
}