[Summer/Winter Coding(~2018)] 스킬트리

[문제 접근법]

- Topology Sort 개념을 적용하여 해당 스킬의 선행스킬이 먼저 배웠는지 확인하였다. 자세한건 아래 소스코드를 보면서 설명하겟습니다.

 

 

토폴로지 정렬이 궁금하다면? 🙄😲

https://m.blog.naver.com/ndb796/221236874984

 

그림 1 - 문제 설명

 

 

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

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

 

---

[구현 1]

1. 선행스킬 그래프와 후행스킬 그래프를 만든다.

2. 스킬트리를 하나씩 루프를 돌아 해당 스킬의 후행 스킬 찾는다.

  2-1. 후행 스킬이 존재한다면 후행 스킬의 선행 스킬을 제거한다.

  2-2. 후행 스킬이 존재하지 않는다면 어떠한 연산도 하지 않는다.

3. 만약 해당 스킬의 선행 스킬이 존재한다면 그 스킬트리는 가능하지 않아서 false를 리턴한다.

4. 스킬트리 루피를 다돌아서 끝나면 해당 스킬트리는 가능하다는 의미로 true를 리턴한다.

 

package com.codingtest.programmers.level2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//Summer/Winter Coding(~2018) > 스킬트리
public class SkillTree {

    public List<Map<String, String>> makePriorSkillMap(String skill) {
        List<Map<String, String>> list = new ArrayList<>();
        Map<String, String> preSkill = new HashMap<>();     //특정 스킬의 선행스킬을 담는다.
        Map<String, String> postSKill = new HashMap<>();       //특정 스킬의 후위스킬을 담는다.

        char[] skillChars = skill.toCharArray();

        for (int i = 1; i < skillChars.length; i++) {
            preSkill.put(String.valueOf(skillChars[i]), String.valueOf(skillChars[i - 1]));
            postSKill.put(String.valueOf(skillChars[i - 1]), String.valueOf(skillChars[i]));
        }

        list.add(preSkill);
        list.add(postSKill);

        return list;
    }

    //스킬트리가 가능한지 확인
    public boolean isPossibleSkillTree(Map<String, String> preSkillMap, Map<String, String> postSKillMap, String skillTree) {
        Map<String, String> preSkill = new HashMap<>(preSkillMap);     //선행 스킬
        Map<String, String> postSkill = new HashMap<>(postSKillMap);   //후위 스킬

        for (char c : skillTree.toCharArray()) {
            String skill = String.valueOf(c);

            //선행 스킬이 있으면
            if (!preSkill.getOrDefault(skill, "0").equals("0"))
                return false;

            else {
                //해당 스킬의 다음 스킬을 찾는다
                String next = postSkill.getOrDefault(skill, "0");
                if (!next.equals("0"))   //해당 스킬의 다음 스킬이 있으면
                    preSkill.put(next, "0");

            }
        }

        return true;
    }

    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        Map<String, String> preSkillMap = makePriorSkillMap(skill).get(0);   //선행 스킬
        Map<String, String> postSKillMap = makePriorSkillMap(skill).get(1);   //후위 스킬

        for (int i = 0; i < skill_trees.length; i++) {
            if (isPossibleSkillTree(preSkillMap, postSKillMap, skill_trees[i]))
                answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        String skill = "CBD";
        String[] skillTrees = {"BACDE", "CBADF", "AECB", "BDA"};

        SkillTree st = new SkillTree();
        int solution = st.solution(skill, skillTrees);

        System.out.println("solution = " + solution);

    }
}