[프로그래머스][C++] 스킬트리

문제

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

프로그래머스

 

풀이

1️⃣ queue

1. 알파벳 개수(26) 크기의 배열로 순서와 상관없는 스킬(true)과 선행 스킬이 필요한 스킬(false)을 표시한다.
2. 스킬의 순서 비교를 위해 큐를 생성하여 skill 값을 할당한다.
3. skill_trees 내의 문자열 탐색
    (1) 선행 스킬이 필요없는 스킬은 무시한다.
    (2) 선행 스킬이 필요한 스킬일 경우, 큐를 이용해 순서가 같은지 확인한다. (queue.front()와 비교)
         - 순서가 같으면 큐에서 해당 문자를 제거한다.
         - 순서가 다르면 answer - 1 한 후, 다음 문자열을 탐색한다.

 

🚨 skill_trees의 문자열을 탐색할 때마다 큐를 초기화해야 한다.

 

2️⃣ string::find()

1. skill_trees 내의 문자열을 탐색하면서 skill과 같은 문자가 있는지 string의 find 함수를 이용해 찾는다. 
    같은 문자가 있으면 이를 string s에 저장한다.
2. s와 skill의 순서를 비교한다.
    순서가 다르면 answer - 1 한 후, 다음 문자열을 탐색한다.

 

🚨 skill_trees의 문자열을 탐색할 때마다 같은 값을 저장하는 string s를 초기화해야 한다.

🚨 순서를 비교할 때 skill이 아닌 s의 길이만큼 비교해야 한다. 선행 스킬 내의 모든 스킬을 배우지 않았어도, 순서를 따르면 조건을 만족하기 떄문이다.

코드

1️⃣ queue

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = skill_trees.size();
    vector<bool> alphabet(26, true);    // 순서와 상관없는 스킬 저장

    for (char c: skill) {
        alphabet[c - 'A'] = false;  // 선행 스킬 필요한 스킬: false
    }

    for (string skill_tree: skill_trees) {
        queue<char> skill_queue;    // 선행 스킬
        for (char c: skill) { // 선행 스킬 삽입
            skill_queue.push(c);
        }

        for (char c: skill_tree) {
            if (alphabet[c - 'A']) {  // 선행 스킬 필요 없음
                continue;
            } else if (c == skill_queue.front()) {   // 선행 스킬 조건 만족
                skill_queue.pop();
            } else {    // 선행 스킬 조건 불만족
                answer--;
                break;
            }
        }
    }

    return answer;
}

 

2️⃣ string::find()

#include <iostream>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = skill_trees.size();
    string s = "";
    
    for(string skill_tree: skill_trees){
        for(char c: skill_tree){
            // skill에 skill_tree와 같은 값이 있으면 저장
            if(skill.find(c) != string::npos){  
                s.push_back(c);
            }
        }
        
        for(int i = 0; i < s.length(); i++){
            if(skill[i] != s[i]){   // 순서가 다르면 불가능한 스킬트리
                answer--;
                break;
            }
        }
        
        s = ""; // 초기화
    }
    
    return answer;
}