JArchive 프로그래밍 일기

문제

스킬 트리 프로그래머스 level2

리뷰

스킬트리에서 스킬에 포함된 문자만 벡터에 넣는다.

스킬의 인덱스와 스킬트리에서 뽑아낸 인덱스가 일치하는지 확인한다.

예를 들어, 스킬 "CBD" , 스킬트리는 "BACDE" 일 때 아래의 과정을 거친다.

스킬 "CBD" 에서. 차례로 "B", "A", "C" ... 를 찾아본다.

for (int j = 0; j < str.size(); j++) { // 스킬트리 문자열을 순회 
    int idx = skill.find(str[j]); // 스킬에서 문자가 발견되는지(포함되는지)
    if (idx != -1) v.push_back(idx); // 스킬에 없는 문자라면 -1 
}
// 반복문이 끝나면 벡터 v에 저장되는 원소들 {1, 0, 2}

왜냐하면 스킬에서 B를 찾으면 idx == 1

스킬에서 A를 찾으면, 없으니까 idx == -1 (push 안 한다)

스킬에서 C를 찾으면, idx == 0

스킬에서 D를 찾으면 idx == 2

스킬의 인덱스와 벡터에 들어간 인덱스가 일치하는지 확인한다.

for (int k = 0; k < v.size(); k++) { // 벡터 v의 크기 만큼 순회
    // 스킬의 인덱스와 벡터의 인덱스가 일치하는지 확인 
    if (v[k] != k) {
        flag = false; break;
    }
} 

코드

#include <string>
#include <vector>
using namespace std;

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

    int skill_len = skill.length(); // 스킬 문자열의 길이 
    int answer = 0;

    for (int i = 0; i < skill_trees.size(); i++) { // 스킬트리들의 개수 만큼 반복  
        string str = skill_trees[i]; // 스킬트리 하나. 
        vector<int> v;

        for (int j = 0; j < str.size(); j++) { // 스킬트리 문자열을 순회 

            int idx = skill.find(str[j]); // 스킬에서 문자가 발견되는지(포함되는지)
             if (idx != -1) v.push_back(idx); // 스킬에 없는 문자라면 -1 
        }

        bool flag = true;

        for (int k = 0; k < v.size(); k++) { 
            // 스킬의 인덱스와 벡터의 인덱스가 일치하는지 확인 
            if (v[k] != k) {
                flag = false; break;
            }
        }

        if (flag) answer++;
    }

    return answer;
}

참고할 만한 코드

'스킬'에 포함되지 않은 알파벳을 전부 지운다. erase() 이용.

/*
스킬이 "CBD" 라면,  
"BACDE"--> "AE" 
"AECB" --> "CB" 
"CBADF"--> "CBD"
*/

제거 후의 문자열의 길이 만큼 '스킬' 알파벳을 확인한다.

"CB"가 결과물인 경우, 스킬도 "CB"까지만 확인한다. 일치한다면 '가능한 스킬트리'다.

#include <string>
#include <vector>
using namespace std;

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

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

        // 스킬 순서에 포함되지 않는 스킬들 제거.
        for (int j = 0; j < skill_trees[i].size(); j++) {

            if (skill.find(skill_trees[i][j]) == string::npos) {

                skill_trees[i].erase(j, 1); // j인덱스부터 1개 제거.
                // erase 함수가 실행되면 배열의 뒷 요소들이 자동으로 한칸씩 당겨짐.
                // j 인덱스 감소시켜야 모든 원소를 빠짐없이 확인 가능.
                j--;
            }    
        }
        // 스킬순서 문자열 에서 skill_trees[i] 문자열 길이만큼 잘라낸다 
        string temp = skill.substr(0, skill_trees[i].size()); 

        if (skill_trees[i] == temp) {
            answer++;
        }        
    }

    return answer;
}