[프로그래머스] 서머코딩/윈터코딩(~2018) - 스킬트리

* 잘못된 풀이

처음에 문제 이해를 잘 못 해서 30분을 날렸다..

분명 마지막 케이스로 BD만 있으면 안되는건데(무조건 c가 선행되어야 함) 계속 연속성만 판단해서 왜 안되나.. 고민하고.. 프린트 해보면서 알게 되었다. 내 잘못이 무엇인지.

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

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string str1;
    int b, tmp;
    vector<int> v1;
    
    for(int i=0; i<skill_trees.size(); i++){
        b = 0;
        for(int j=0; j<skill.size(); j++){
            str1 = skill_trees[i];
            tmp = str1.find(skill[j]);
            cout << tmp;
            if(tmp<0 || tmp>=26) continue;
            else v1.push_back(tmp);
        }
        cout << endl;
        for(auto iter:v1){
            cout << iter;
        }
        cout << endl;
        for(int j=0; j<v1.size(); j++){
            if(j!=v1.size()-1 && v1[j]>v1[j+1]){
                b=1;
                break;
            }
        }
        v1.clear();
        if(b==0)
            answer++;
    }
    return answer;
}

 

그래서 반대로 생각해보았다.

(알고리즘)

1. skill에 있는 문자를 skill_trees에서 찾았는데, 반대로 skill_trees에 있는 문자를 skill에서 찾기.

2. check 값으로 순차대로 스킬이 진행되는지 확인하기

    (1) find 한 값이 check와 일치하지 않으면 순차대로 스킬이 진행되지 않았단 의미이므로

        불가능한 스킬임을 알리는 flag를 0으로 설정 후 break.

    (2) find 한 값이 0보다 작고 25보다 크다면 문자열에 포함되지 않았단 의미이므로 continue.

    (3) 그 외는 check++

3. flag가 1이면 answer++

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

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int flag, check;
    string str1;
    
    for(int i = 0; i < skill_trees.size(); i++){
        check = 0;
        flag = 1;
        str1 = skill_trees[i];
        for(int j = 0; j < str1.size(); j++){
            int tmp = skill.find(str1[j]);
            if(tmp < 0 || tmp > 25){
                continue;
            }
            else if(tmp != check){
                flag = 0;
                break;
            }
            else{
                check++;
            }
            
        }
        if(flag){
            answer++;
        }
    }
    return answer;
}