쌓고 쌓다
[프로그래머스] 스킬트리 C++ 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/49993
풀이 방법
map에 해당 스킬과 해당 스킬을 배우기 위해 필요한 스킬들의 개수를 담을 것입니다.
이렇게 담아놓으면 나중에 스킬 트리를 앞에서부터 읽으면서 해당 스킬을 배울 때 필요한 스킬 개수가 0이라면
바로 배우면 되는 것입니다.
하지만! 해당 스킬을 배울 때 필요한 개수가 0이 아니라면
선행 스킬을 다 배우지 않은 것인데 배울 수 없는 스킬임을 판별할 수 있습니다.
이때 현재까지 배워둔 스킬의 개수를 cnt 변수로 관리하면 편리합니다.
전체 코드
#include <string>
#include <vector>
#include <map>
using namespace std;
int solution(string skill, vector<string> skill_trees) {
int answer = 0; // 가능한 개수(-1 => 0)
map<char,int> m; // <스킬, 이스킬을 배우기위한 선행 스킬의 개수>
for(int i=0; i<skill.length(); i++) {
m.insert({skill[i], i}); // 스킬을 배우기위해 앞서 배워야하는 스킬 개수
}
for(int i=0; i<skill_trees.size(); i++) {
bool able = true; // 이 스킬트리가 가능한가?
int cnt = 0; // 현재까지 몇개의 스킬을 배웠는가?
// 스킬트리 탐색
for(int j=0; j<skill_trees[i].length(); j++) {
if(m.find(skill_trees[i][j]) != m.end()) { // skill에 존재하는 문자라면
if(m[skill_trees[i][j]] != cnt) { // 내가 앞서 배운 스킬들의 개수와 일치하는가?
able = false; // 일치하지 않으면 선행스킬이 올바르지 않은것임.
break;
} else { // 앞서 배워야할 개수와 일치하면 해당 스킬 획득
cnt++;
}
}
}
if(able) { // 이 스킬트리가 가능한가?
answer++;
}
}
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 방문 길이 C++ 풀이 및 해설 (0) | 2023.03.24 |
---|---|
[프로그래머스] 땅따먹기 C++ 풀이 및 해설 (0) | 2023.03.20 |
[프로그래머스] 할인 행사 C++ 풀이 (0) | 2023.03.05 |
[프로그래머스] [3차] n진수 게임 C++ 풀이 (0) | 2023.03.03 |
[프로그래머스] 연속 부분 수열 합의 개수 C++ 풀이 (0) | 2023.01.23 |
Comments