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

문제

 

분석

특별히 분석할게 없었다.

그냥 CBD 라면 스킬트리에서 해당 인덱스를 따로 저장한다.

skill_trees의 BACDE 에서 C, B, D 각각의 index를 찾는다.

C = 2, B = 0, D = 3

 

인덱스 순으로 보면

B(0), C(2), D(3) 순으로 스킬을 익혔기 때문에 BACDE 를 위반한다.

불가능함.

 

위처럼 1차검사

2차 예외 상황 선행스킬 하나만 찍었을때 

3차 선행스킬 존재 하지 않을때  각각의 예외상황을 처리해 주었다.

 

코드

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

bool checkOrderFunction(string aSkill, string aSkillTree);

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    // skill tree에서 하나씩 꺼내 가능성을 체크한다.
    for(int i = 0; i <skill_trees.size(); i++)
    {
        if( checkOrderFunction(skill, skill_trees[i]) ){
            answer++;
        }
    }
    
    return answer;
}


bool checkOrderFunction(string aSkill, string aSkillTree)
{
    
    // skill index 초기화
    int checkOrderArry[10001];
    for (int i = 0; i < aSkill.size(); i++)
    {
        checkOrderArry[i] = -1;
    }
    
    // skill tree 에서 skill의 index 찾아 넣어준다.
    for (int i = 0; i < aSkill.size(); i++)
    {
        string::size_type loc = aSkillTree.find(aSkill.at(i), 0);
        int num = loc;
        if (loc < aSkillTree.size()) {
            checkOrderArry[i] = num;
        }
    }
    
    bool notFindFlag = false;
    for (int i = 0; i < aSkill.size(); i++)
    {

        // 선행 스킬을 안찍고 다음 스킬을 찍었으면 불가
        if (notFindFlag) {
            if (checkOrderArry[i] != -1) {
                return false;
            }
        }
        
        // 해당 스킬을 스킬트리에서 못찾음.
        if (checkOrderArry[i] == -1) {
            notFindFlag = true;
            continue;
        }
        
        // 선행스킬대로 순서가 되어 있는지 검사. 다음 스킬이 존재하지 않으면 못찾았다는 걸 표시
        // 선행스킬보다 먼저 찍었는지 검사.
        // -1 이라면 다음 스킬을 안찍었다는 것을 표시
        if (checkOrderArry[i] > checkOrderArry[i+1] && i+1 < aSkill.size()) {
            if (checkOrderArry[i+1] == -1) {
                notFindFlag = true;
                continue;
            }
            return false;
        }
    }
    
    // 정상적으로 되어 있으면 true
    return true;
}

 

TEST 결과

 

 

 

 

문제링크:

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

코딩테스트 연습 - 스킬트리