프로그래머스 - 스킬트리 - C++

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

문제 설명

• 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성하는 문제이다.

접근 방법

• 문제는 skill_trees 에서 skill_tree를 하나씩 꺼내 skill과 비교하여 스킬을 찍는 순서가 같은 skill_tree를 카운트 하는 방식으로 접근하였다.

• 접근 방식의 로직이 크게 어렵지 않고, 제한조건은 skill의 길이가 1~26, skill_trees의 size는 1~20, skill_tree의 길이가 2~26 이므로 3중 for문을 사용해도 큰 무리가 없어보인다.

코드

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

bool ch[26];
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    char a;
    int no=0;	// 불가능한 스킬트리의 수를 count 할 변수
    
    for(int i=0;i<skill_trees.size();i++){
        memset(ch,false,sizeof(ch));	// ch 초기화
        
        for(int j=0;j<skill_trees[i].size();j++){
        
            for(int k=0;k<skill.length();k++){
            
                if(skill[k]==skill_trees[i][j]){
                
                    if(k==0 || ch[k-1]){	// 첫번째 skill 이거나, 이전 skill이 찍혔다면
                        ch[k] = true;
                    }
                    else{	// 불가능한 skill_tree라면 
                        j=skill_trees[i].size();	
                        k=size;
                        no++; // count
                    }
                    
                }
                
            }            
        }
    }
    
    answer = skill_trees.size()-no; // answer 값 계산
    return answer;
}

결과

느낀점

• 불가능한 skill_tree를 만나면 탈출하는 로직 조금 억지같은가...? ㅎㅎ
  누구 좋은 로직 있으시면 댓글 남겨주세요.