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

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

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

 

skill_trees에 있는 스킬트리중 익힐수 있는 스킬트리의 갯수를 출력하는 문제입니다.

 

문제 접근법

• skill_trees의 원소에 접근해야하고, skill의 각각의 문자들을 skill_tress원소의 길이만큼 확인해야 하므로 3중 for문을 사용하면 좋을것 같다는 생각을 할 수 있습니다.
• skill의 최대 길이는 26, skill_trees의 최대 길이는 20, skill_trees의 원소의 최대 길이는 26입니다 그러므로 시간복잡도는 26 * 20 * 26으로 3중 for문을 사용해도 괜찮다는 결론이 나옵니다.
• 3중 for문을 돌며 skill의 원소와 skill_trees의 각 배열의 원소들을 비교합니다.
  • 스킬이 올바른 순서대로 배웠는지 체크하기 위한 index값을 하나 둡니다.
  • 최후에 스킬 스킬 순서를 확인하기위해 vector<int> v를 하나 둡니다.
  • 중간 종료 체크를 위한 플래그값을 둡니다.
  • skill에 해당하는 원소가 skill_trees에 있을 경우 해당 index값을 체크한 뒤 v에 index값을 넣고 계속 진행합니다.
  • 다음에 skill에 해당하는 원소가 index값보다 앞에 있을 경우 올바르지 않은 스킬트리이므로 종료플래그를 설정하고 다음 skill_trees로 넘어갑니다.
• 3중 for문 1바퀴가 돌고 나면 v의 size를 확인합니다.
  • v의 size가 1이고, 중간 종료가 되지 않았다면 v[0]이 0인지 확인합니다.
    • v[0]이 0인 경우 첫번째 순서의 스킬이 들어온게 맞으므로 answer을 증가시켜줍니다.
    • v[0]이 0이 아닌 경우 스킬이 순서대로 들어온것이 아니므로 answer는 증가하지 않습니다.
  • v size가 1 이상이고, 중간 종료가 되지 않았다면 v[0]이 0인지 확인합니다.
    • v[0]이 0인 경우, for 문을 돌면서 v[i] + 1 == v[i + 1] 이 성립하는지 확인합니다. 성립 할 경우 모든 스킬이 순서대로 들어온 것이므로, answer을 증가시켜줍니다.
    • 위와 다른 경우 스킬이 순서대로 들어온것이 아니기 때문에 answer은 증가하지 않습니다.

 

아래는 코드입니다.

#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<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(j);
                    }
                }
            }      
            if(check) 
                break;
        }
                
        if(v.size() > 1 && !aCheck)
        {
            for(int j = 0; j < v.size() - 1; j++)
            {
                if(v[0] != 0)
                {
                    aCheck = true;
                    break;
                }
            
                if(v[j] != v[j + 1] - 1)
                {
                    aCheck = true;
                    break;
                }
            } 
        }
        else if(v.size() == 1 && !aCheck)
        {
            if(v[0] != 0) 
                aCheck = true;
        }
        
        if(!aCheck) 
            answer++;
    }
   
    return answer;
}

 

아래 코드는 위의 코드를 개선한 코드입니다.

#include <string>
#include <vector>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    bool check;
 
    for(int i = 0; i < skill_trees.size(); i++)
    {
        vector<int> v;
 
        for(int j = 0; j < skill_trees[i].size(); j++)
            for(int k = 0; k < skill.size(); k++)
                if(skill_trees[i][j] == skill[k])
                    v.push_back(skill_trees[i][j]);
 
        check = false;
 
        for(int j = 0; j < v.size(); j++)
        {
           if(skill[j] != v[j])
           {
               check = true;
               break;
           }
        }
 
        if(!check) 
            answer++;
    }
    
    return answer;
}