[프로그래머스]Summer/Winter Coding(~2018) : 스킬트리 (level 2) (c++)

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

프로그래머스

 

 

 

#include <string>
#include <vector>

using namespace std;

// 각 문자열의 스킬 순서가 가능한 스킬트리인지 검사
bool possible(int input_order[], string &tree)
{
    int t_order = 1;
    for (int i = 0; i < tree.size(); ++i)
    {
        // 선행스킬 목록에 주어진 스킬만 검사
        if (input_order[tree[i] - 'A'])
        {
            // 선행스킬과 순서가 다르면 false 리턴
            if (input_order[tree[i] - 'A'] != t_order)
            {
                return false;
            }
            // 같으면 인덱스 증가
            ++t_order;
        }
    }

    return true;
}

int solution(string skill, vector<string> skill_trees) {
    
    // 선행스킬로 주어진 스킬트리 순서 입력
    const int MAX = 26;
    int input_order[MAX] = { 0, };
    int order = 1;
    for (int i = 0; i < skill.size(); ++i)
    {
        input_order[skill[i] - 'A'] = order++;
    }
    
    // 각 스킬 트리 검사
    int answer = 0;
    for (int i = 0; i < skill_trees.size(); ++i)
    {
        if (possible(input_order, skill_trees[i]))
        {
            ++answer;
        }
    }

    return answer;
}

 

 

입력이 최대 26까지 (알파벳 길이) 이므로, 

크기가 26인 int배열을 만들어서 들어온 순서대로 값을 매긴다. 

 

예를 들어 C → B → D 로 들어왔다면

arr[B] = 2, arr[C] = 1, arr[D] = 3  이런식으로.

 

어차피 앞에서부터 비교해 나갈거니까, 

주어진 스킬트리와 순서가 같지 않으면 바로 FALSE!