[C++로 풀이] 스킬트리⭐⭐

📌 스킬트리

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;

    for (int i = 0; i < skill_trees.size(); i++)
    {
        int pos = -1;
        bool impossible = false;
        char impossibleChar = skill[0];
        for (int j = 0; j < skill.length(); j++)
        {
            if (j != skill.length())
                impossibleChar = skill[j + 1];

            for (int k = 0; k < pos; k++)
            {
                if (skill[j] == skill_trees[i][k])
                {
                    impossible = true;
                    break;
                }
            }

            for (int k = pos + 1; k < skill_trees[i].length(); k++)
            {
                if (skill[j] == skill_trees[i][k])
                {
                    pos = k;
                    break;
                }
                else if (impossibleChar == skill_trees[i][k])
                {
                    impossible = true;
                    break;
                }
            }
        }

        if (!impossible)
            answer++;
    }

    return answer;
}

• 예를 들어 skill이 “CBD”이며 가능한 스킬 트리인지 검사하려는 대상이 “BACDE”라면
  • “C”
    • C가 3번째에 있다. ⭕ C의 위치를 저장한다.
  • “B”
    • C의 ‘앞’에 B가 있다. ⭕
      • 👉 불가능한 스킬트리
• 예를 들어 skill이 “CBD”이며 가능한 스킬 트리인지 검사하려는 대상이 “BDF”라면
  • “C”
    • C가 없다. ❌ 따라서 impossibleChar 에 다음 글자인 "B"를 저장한다. 다음에 "B" 검사할 때 B가 C 앞에 오면 안되는 것을 기억해야 하기 때문
  • “B”
    • C의 ‘앞’에 B가 있다. ⭕
      • 👉 불가능한 스킬트리
• 예를 들어 skill이 “CBD”이며 가능한 스킬 트리인지 검사하려는 대상이 “ACDE”라면
  • “C”
    • C가 2번째에 있다. ⭕ C의 위치를 저장한다.
  • “B”
    • C의 ‘뒤’에 B가 없다. ❌ (없어도 됨. 스킬트리에 꼭 CBD가 다 들어가야하는건 아니다. 강화 가능 순서만 지키면 될 뿐.) B의 위치를 저장한다.
  • “D”
    • B의 ‘뒤’에 D가 있다. ⭕ D의 위치를 저장한다.
  • 반복문 전체 도는 동안 한번도 break 되지 않았으므로 이 스킬은 가능한 스킬트리이다.

🚀 다른 풀이

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, int> numberOf;

    for (int i = 0; i < skill.length(); i++)
        numberOf[skill[i]] = i + 1;

    for (int i = 0; i < skill_trees.size(); i++)
    {
        int current = numberOf[skill[0]]; // 첫 글자의 가치부터 차례 차례 
        bool possible = true;

        for (int j = 0; j < skill_trees[i].size(); j++)
        {
            if (current < numberOf[skill_trees[i][j]])
            {
                possible = false;
                break;
            }
            else if (current == numberOf[skill_trees[i][j]])
                current++;
        }
        
        if (possible) answer++;
    }

    return answer;
}

코드는 멍토님 블로그 를 참고하였다.

map 의 Key, Value

• 예를 들어 skill이 “ACBED”이라면
  • 맵을 통하여 비교 기준이 되는 가치를 부여 “C”는 1, “B”는 2, “D”는 3.

    map<char, int> numberOf;
    for (int i = 0; i < skill.length(); i++)
        numberOf[skill[i]] = i + 1;
    

  • 가치가 더 작은게 반드시 가치가 큰것 보다 앞에 위치해야 한다!
  • current에는 차례대로 “C”, “B”, “D” 의 가치인 1, 2, 3 으로 차례로 갱신된다.
  • “A”와 “E”같이 map 에 없는 문자들은 알아서 numberOf[skill_trees[i][j]]만 실행해도 Value 값이 0 인 Key 로서 추가가 된다. map 의 특징!
    • 정해진 스킬 순서에 없는 “A”와 “E”는 정해진 스킬 순서에 속한 문자들보다 가치가 작아 이들보다 앞에 오더라도 문제가 없게 해야한다. 다행히 map에 추가하면 알아서 int 디폴트 값인 0으로 Value가 설정 됨.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기