[프로그래머스 / Level 2] 스킬트리

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

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

문제 접근법

• skill 문자열에 있는 문자를 skill_trees에 있는 문자열에 있는 문자와 하나씩 비교한다.
• 해당하는 단어가 있을경우 skill의 몇번째 위치의 문자인지와 skill_trees의 원소의 몇번째 자리인지를 체크하여 pair로 vector에 넣어준다.
  • 만약 다음 문자가 이전 문자의 위치보다 앞에 있다면 틀린 스킬 트리이므로 다음 스킬 트리를 검사한다.
• vector의 사이즈가 1보다 크고 skill_trees의 원소를 모두 체크한 경우
  • vector의 맨 앞값의 first가 0이 아니라면, 스킬 트리의 순서가 틀린것이므로, 다음 스킬트리를 검사한다.
  • 검사하는 vector값의 first와 다음 값의 first가 1차이가 나지 않는다면 스킬 트리의 순서가 틀린것이므로, 다음 스킬트리를 검사한다.
• vector의 사이즈가 1이고 skill_trees의 원소를 모두 체크한 경우
  • vector의 맨 앞값의 first가 0이 아니라면, 스킬 트리의 순서가 틀린것이므로, 다음 스킬트리를 검사한다.
• 앞에서 해당되는 내용이 없으면 올바른 스킬트리이므로, return 할 값을 증가시켜준다.

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int len = skill_trees.size();
    int sLen = skill.size();
    
    for(int i = 0; i < len; i++)
    {
        int stLen = skill_trees[i].size();
        int sIndex = 0;
        bool check = false;
        bool aCheck = false;
        
        vector<pair<int, int>> v;
        
        for(int j = 0; j < sLen; j++)
        {   
            for(int k = 0; k < stLen; k++)
            {
                if(skill[j] == skill_trees[i][k])
                {
                    if(sIndex > k)
                    {
                        check = true;
                        aCheck = true;
                        break;
                    }
                    else
                    {
                        sIndex = k;
                        v.push_back(make_pair(j, sIndex));
                    }
                }
            }      
            if(check) break;
        }
                
        if(v.size() > 1 && !aCheck)
        {
            for(int j = 0;  j < v.size() - 1; j++)
            {
                if(v[0].first != 0)
                {
                    aCheck = true;
                    break;
                }
            
                if(v[j].first != v[j + 1].first - 1)
                {
                    aCheck = true;
                    break;
                }
            } 
        }
        else if(v.size() == 1 && !aCheck)
        {
            if(v[0].first != 0) aCheck = true;
        }
        
        if(!aCheck) answer++;
    }
   
    return answer;
}