[알고리즘 풀이 분석] 프로그래머스 스킬 트리

오늘 풀어본 두가지 문제 중 좀 더 가벼운 프로그래머스 스킬 트리 리뷰!

프로그래머스 스킬 트리

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 파크 → 라이트닝 볼트 → 썬더때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 파크 → 힐링 → 라이트닝 볼트 → 썬더 같은 스킬트리는 가능하지만, 더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더 같은 스킬트리는 불가능합니다.

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

입출력

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

나의 풀이

아주 간단한 문제이다. 주어진 skill 의 순서대로 글자들이 나열 되었는지만 확인하면된다. 간단한 문제이기 때문에 다양한 방법으로 구현이 가능할 것 같다.

나의 경우에는 주어진 skill 의 순서대로 번호를 짝지어 {'C' - 0}과 같이map에 저장하였다.탐색이 진행될 때 바로바로 해당 문자의 순서를 확인할 수 있도록 하기 위함이다.

이후 skill_trees 의 문자열들을 탐색하면서 나온 문자가 map 에 존재하지 않는다면 그대로 탐색을 진행, 존재 한다면 올바르게 나와야 하는 문자의 번호와 일치하는지를 확인해 주었다.

코드

c++

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, int> skill_order;

    for (int i = 0; i < skill.size(); ++i) {
        skill_order.insert({skill[i], i});
    }

    for (int i = 0; i < skill_trees.size(); ++i) {
        int cur = 0;
        bool able = true;
        for (int j = 0; j < skill_trees[i].size(); ++j) {
            if (skill_order.find(skill_trees[i][j]) == skill_order.end()) continue;
            if (skill_order[skill_trees[i][j]] == cur){
                cur++;
            }else{
                able = false;
                break;
            }
        }

        if (able) answer++;
    }


    return answer;
}

swift

import Foundation

extension String {
    subscript(idx: Int) -> String? {
        guard (0..<count).contains(idx) else {
            return nil
        }
        
        let target = index(startIndex, offsetBy: idx)
        return String(self[target])
    }
}

func solution(_ skill:String, _ skill_trees:[String]) -> Int {
    var answer = 0
    var skill_order : [String : Int] = [:]
    
    for i in 0..<skill.count {
        guard let key = skill[i] else {
            continue
        }
        skill_order[key] = i
    }
    
    for tree in skill_trees {
        var cur = 0
        var able = true
        
        for i in 0..<tree.count {
            guard let key = tree[i] else {
                continue
            }
            
            if let value = skill_order[key] {
                if value == cur {
                    cur += 1
                    continue
                }else{
                    able = false
                    break
                }
            }else {
                continue
            }
            
        }
        
        if able {
            answer += 1
        }
    }
    
    return answer
}