[프로그래머스 스킬트리] c++ (풀이,코드, map)

문제 링크

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

프로그래머스

 

문제

 

 

코드, 풀이

이 문제는 map을 통해서 간단하게 풀 수 있다고 생각합니다.

 

물론 vector에 push_back을 하면서 진행을 해도 괜찮다고 생각을 합니다.

 

최근에 map을 많이 사용하고 있어서 map으로 풀이를 진행하였습니다.

 

1. skill에 대한 인덱스를 넣어줍니다. (향후 비교를 위해)

2. 반복문을 돌면서 같은 idx가 나온다면 idx를 ++ 해줍니다 (1번의 인덱스와 같이 계속 늘어나겠죠.)

3. 순서가 뒤짚힌 것에 대한 체크를 해야하니 map에서 찾았는데 idx보다 크다는 것은 뒤에 와야할것이 먼저 왔으니 break;

4. 끝에 도달하였거나 idx == lastSkill -> 조금이라도 먼저 완성을 했다면  return 합니다.

 

/*

음.. 그냥 반복문 돌면서 확인하면 끝 아닌가?

아 아니다 맵을 사용하면 되겠다.

*/

#include <string>

#include <vector>

#include <map>

using namespace std;

int solution(string skill, vector<string> skill_trees) {

    int answer = 0;

    int lastSkill = skill.length() - 1;

    map<char,int> m;

   

    for(int i = 0; i < skill.length();i++)

        m[skill[i]] = i;

   

    for(int i = 0 ; i < skill_trees.size();i++){

        int idx = 0;

        for(int j = 0; j < skill_trees[i].length();j++){

            if(skill_trees[i][j] == skill[idx])

                idx++;

            else{

                //맵에 존재하고 index가 더 크다 -> 뒤에 스킬이다.

                if(m.find(skill_trees[i][j]) != m.end() && m[skill_trees[i][j]] > idx)

                    break;

            }

            //끝에 도달했거나 idx == lastSkill이라는 것은 이제 스킬을 다 사용.

            if(idx == lastSkill || j == skill_trees[i].length() - 1){

                answer++;

                break;

            }

        }

    }

   

   

    return answer;

}