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

문제

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

필요 지식

1. unordered_map (자료구조 - tree)

해결 방법

단순히 3중 반복문을 하거나 2중 반복문을 통해서 풀어도 되는 문제이지만, 조금 더 효율적이기 위해 시간복잡도가 O(1)인 unordered_map을 사용하였다. O(logn)의 시간복잡도를 가지는 map을 가지고 풀어도 같은 풀이가 된다.

 

unordered_map을 사용한 이유는 skill의 알파벳과 순서를 동시에 기억할 자료구조가 필요했기 때문이다. 

따라서, skill의 알파벳과 순서를 동시에 기억할 수 있는 unordered_map을 사용해서 해당 문자에 스킬 순서를 넣었다. 그 후, skill tree에서 skill에 해당하는 문자의 순서가 본래 순서와 맞게 간다면 answer의 수를 늘렸다. 

이를 위해서 temp를 사용했다. temp는 본래의 순서에 해당한다. flag도 있는데, flag는 순서가 맞지 않는 것을 발견했을때의 단순 지표이다. 

코드

효율