프로그래머스 Lv.2) 스킬트리

스킬트리

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

풀이

(2020.05.16)

 

스킬을 찍어야하는 순서를 ArrayList에 char로 담아주었다. 또한, char를 담으면서 해당 스킬이 ArrayList에 부여된 인덱스 넘버를 HashMap을 통해 저장해주었다. 이후, 스킬 트리 배열을 돌면서 String값을 검증했다. 

우선 모든 스킬이 가능하다는 가정을 두고 스킬트리 배열의 길이 만큼 return할 결과에 담아주었다.

String을 돌 때마다 해당 SkillTree를 위한 ArrayList에 스킬을 저장하면서 확인했다.

String의 index마다 그 스킬이 찍어야하는 스킬 ArrayList에 담겨있는지 먼저 확인하고, 배워야하는 스킬이면 이 스킬 이전에 배워야하는 스킬을 배웠는지 확인한다. 만약, 이전 스킬을 배우지 않았다면 돌고있는 스킬 순서 String을 종료하면서 return할 값을 1씩 감소시켰다.

 

(2020.06.04)

처음 풀이보다 조금 더 간략하게 풀었다.

HashMap을 사용하면서 index를 파악하면 빠르지 않을까 싶어서, HashMap을 사용했는데 처음 풀이에도 HashMap이 있었다.. ㅋㅋㅋ

다른점은 ArrayList에 저장하는 과정과, 담겨져있는지 확인하는 과정을 생략했다는 점이다.

각 Skill tree마다 앞서 배운 스킬의 인덱스 번호인지만 확인해주었다.

반복문 시작시점에 idx = 0으로 초기화해주고(스킬은 1번부터 시작되기 때문에), 미리 저장해둔 Map에 해당 스킬이 포함되어 있는지 확인해준다. (선행스킬이 필요한 스킬인지 확인)

필요하다면, 해당 스킬이 지닌 인덱스 번호를 불러와서, 이전에 배운 인덱스 번호인지 확인해주고 아니라면 count에서 하나를 빼주고, 반복문을 종료하였다.

 

코드 1

 

import java.util.ArrayList;
import java.util.HashMap;

public class SkillTree_49993 {
    static HashMap<Character,Integer> skillMap;
    private static int solution(String skill, String[] skill_trees) {
        skillMap = new HashMap<>();
        ArrayList<Character> skillOrder = getOrderList(skill);

        return getCount(skillOrder, skill_trees);
    }

    private static int getCount(ArrayList<Character> skillOrder, String[] skill_trees) {
        int result =skill_trees.length;
        ArrayList<Character> checkList = new ArrayList<>();

        for(String str : skill_trees) {
            for(int i=0; i<str.length(); i++) {
                char skill = str.charAt(i);
                if(skillOrder.contains(skill)) {
                    int order = skillMap.get(skill);
                    if(order != 0) {
                        if(!checkList.contains(skillOrder.get(order-1))) {
                            result--;
                            break;
                        }
                        checkList.add(skill);
                    } else {
                        checkList.add(skill);
                    }
                }
            }
            checkList.clear();
        }
        return result;
    }

    private static ArrayList<Character> getOrderList(String skill) {
        ArrayList<Character> result = new ArrayList<>();
        for(int i=0; i<skill.length(); i++) {
            result.add(skill.charAt(i));
            skillMap.put(skill.charAt(i), i);
        }
        return result;
    }

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

        System.out.println(solution(skill,skill_trees));
    }
}

 

코드 2

 

import java.util.HashMap;
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = skill_trees.length;
        HashMap<Character,Integer> skillMap = new HashMap<>();
        for(int i=0; i<skill.length(); i++) {
            skillMap.put(skill.charAt(i), (i+1));
        }
        for(String str : skill_trees) {
            int idx =0;
            for(int i=0; i<str.length(); i++) {
                char ch = str.charAt(i);
                if(skillMap.containsKey(ch)) { // 스킬 순서가 필요한 경우
                    if(skillMap.get(ch) != idx+1) { // 순서에 안맞는 경우
                        answer--;
                        break;
                    }
                    idx++;
                }
            }
        }
        return answer;
    }
}