Programmers - 스킬트리

---

title: Programmers - 스킬트리
date: 2022-07-08
tags:

• Algorithm

---

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

문제 요약

선행 스킬의 순서와 자유로운 스킬트리가 주어진다. 순서를 벗어난 스킬트리는 사용할 수 없으며, 사용 가능한 올바른 스킬트리의 개수를 return한다.

문제 풀이

선행 스킬의 순서는 최대 26개, 스킬트리는 최대 20개가 존재하며 각각 최대 26개의 순서로 구성되어 있다.
시간 복잡도는 문제가 없을 것이며, 구현만 하면 되는 문제이다.

처음에는 선행 스킬의 뒤부터 검사를 하는 프로그램을 작성하였으나, for문을 3번 중첩해야 하는 프로그램이 되었다.
unordered_map을 도입하여 2개의 for문 중첩으로 바꾸었다.
선행 스킬의 처음부터 1씩 증가하는 값으로 지정하고, 각 스킬별로 값을 비교하였다.
현재 n이라면 n+1 혹은 자유로운 스킬만 배울 수 있으며, 그보다 높은 값이 들어오면 순서가 어긋나기에 잘못된 스킬트리라 판단한다.
unorderd_map은 Hash function이 있기에 O(1)로, 이를 사용하여 성능 측면에서 개선하였다는 것을 알 수 있다.

프로그램

#include <string>
#include <vector>
#include <unordered_map>

using std :: string ;
using std :: vector ;
using std :: unordered_map ;

int solution ( string skill , vector < string > skill_trees )
{
    int iAnswer = 0 ;
    int iLen = skill.length () ;
    int iTreeCount = skill_trees.size () ;
    const char * cpTemp = skill.data () ;
    unordered_map < char , int > umOrder ;



    for ( int i = 0 ; i < iLen ; ++i )
    {
        umOrder [ cpTemp [ i ] ] = i + 1 ;
    }
    for ( int i = 0 ; i < iTreeCount ; ++i )
    {
        iLen = skill_trees [ i ].size () ;
        int iMapValue = 0 ;
        cpTemp = skill_trees [ i ].data () ;

        for ( int j = 0 ; j < iLen ; ++j )
        {
            if ( 0 != umOrder [ cpTemp [ j ] ] )
            {
                if ( iMapValue + 1 == umOrder [ cpTemp [ j ] ] )
                    ++ iMapValue ;
                else
                {
                    -- iAnswer ;

                    break ;
                }
            }
        }

        ++ iAnswer ;
    }


    return iAnswer ;
}