프로그래머스 - 스킬트리

프로그래머스 - 스킬트리

제한 조건

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

skill로 주어진 문자열이 중복이 없기 때문에 그냥 hash로 치환해서 풀 수 있었다.
먼저 hashMap에 체크해둔다. 그리고 문자열에서 hashMap에서 체크된 문자열을 만날 때마다 주어진 조건을 만족하는지 체크하면 된다.
right는 0부터 시작하면서 1씩 증가한다. hashMap에 체크된 문자열을 만날 때, skill[right]와도 같은지 체크하면 문제에서 주어진 조건을 만족시키는 문자열인지를 체크할 수 있다. (C->B->D 형태)
만약 hashMap에는 체크되었지만 skill[right]와 같지 않다면 C->D->B 형태의 문자열이라는 것이기 때문에 answer를 증가시키면 안된다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int hashMap[30]; memset(hashMap, 0, sizeof(hashMap));
    for(int i=0;i<skill.size();i++) 
        hashMap[skill[i] - 'A'] = 1;
    
    for(int i=0;i<skill_trees.size();i++) {
        string s = skill_trees[i];
        int right = 0, wrong = 0;
        for(int j=0;j<s.size();j++) {
            if(hashMap[s[j]-'A']) {
                if(s[j] != skill[right]) {
                    wrong++;
                    break;
                }
                right++;
            }
        }
        if(wrong == 0)
            answer++;
    }
    return answer;
}