[프로그래머스] Lv.2 : 스킬트리 - 자바[Java]

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

프로그래머스

 

풀이

skill_trees에 저장된 각 스킬 트리가 가능한 스킬트리인지 검사한 후 가능한 스킬트리의 개수를 출력해야 한다.

 

스킬트리가 가능한 스킬트리인지는 skill에 저장되어있는 스킬들의 순서를 통해 알 수 있다.

이를 위해 skill에 저장되어있는 스킬들의 순서를 통해 Map 타입 변수 skillMap을 선언해 (스킬 이름, 스킬 순서)를 저장한다.

이후 skill_trees에 저장된 각 스킬 트리에서 skillMap에 저장된 스킬에 대해서만 가능한 스킬 순서인지 검사하는 메서드를 통해 가능한 스킬 트리인지 확인한다.

 

로직

1. Map<Character, Integer> skillMap을 선언한다. skillMap은 (스킬 이름, 스킬 순서)를 저장한다.

2. skill을 통해 skillMap에 선행 스킬 순서 정보를 저장한다.

3. cnt를 선언하고 0으로 초기화한다.

4. skill_trees의 각 스킬 트리에 대해 countValidateSkill() 메서드를 호출하여 가능한 스킬 트리의 개수를 cnt에 저장한다.

5. cnt를 출력한다.

 

int countValidateSkill(String skill_tree, Map<Character, Integer> skillMap) : skill_tree가 가능한 스킬 트리라면 1을 리턴, 아니면 0을 리턴한다.

    private static int countValidateSkill(String skill_tree, Map<Character, Integer> skillMap) {
        List<Integer> checkIdxList = new ArrayList<>();
        
        for (int i = 0; i < skill_tree.length(); i++) {
            char skill = skill_tree.charAt(i);
            
            if (skillMap.containsKey(skill) && !validateSkillTree(skill, skillMap, checkIdxList)) {
                return 0;
            }
        }
        
        return 1;
    }

• List<Integer> checkIdxList를 선언한다. checkIdxList에는 skill_tree의 스킬들 중 skillMap에 있는 스킬인 경우의  스킬 순서를 저장한다.
• skill_tree에 나온 각 스킬에 대해 다음을 수행한다.
  • 스킬이 skllMap에 있다면, validateSkillTree() 메서드를 호출하여 가능한 스킬트리인지 검사한 후, 가능하지 않다면 0을 리턴한다.
• 가능한 스킬트리라면 1을 리턴한다.

 

private static boolean validateSkillTree(char skill, Map<Character, Integer> skillMap, List<Integer> checkIdxList) : 가능한 스킬트리인 경우 true을 리턴, 아니면 false을 리턴한다.

    private static boolean validateSkillTree(char skill, Map<Character, Integer> skillMap, List<Integer> checkIdxList) {
        int turn = skillMap.get(skill);
        
        if (turn > 0) {
            int idx = checkIdxList.indexOf(turn - 1);
            if (idx == -1)
                return false;
        }
        checkIdxList.add(turn);
        
        return true;
    }

• skillMap에 저장되어 있는 skill의 순서를 구한다.
• 순서가 0보다 크다면, skill의 선행 스킬의 순서가 checkIdxList에 있는지 구한다. 없다면 false를 리턴한다.
• 순서가 0이거나 skill의 선행 스킬의 순서가 checkIdxList에 있다면, checkIdxList에 현재 스킬(skill)의 순서를 추가하고 true를 리턴한다.

 

 

코드

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        Map<Character, Integer> skillMap = new HashMap<>();
        for (int i = 0; i < skill.length(); i++)
            skillMap.put(skill.charAt(i), i);
        
        int cnt = 0;
        for (String skill_tree : skill_trees) {
            cnt += countValidateSkill(skill_tree, skillMap);
        }
        
        return cnt;
    }
    
    private static int countValidateSkill(String skill_tree, Map<Character, Integer> skillMap) {
        List<Integer> checkIdxList = new ArrayList<>();
        
        for (int i = 0; i < skill_tree.length(); i++) {
            char skill = skill_tree.charAt(i);
            
            if (skillMap.containsKey(skill) && !validateSkillTree(skill, skillMap, checkIdxList)) {
                return 0;
            }
        }
        
        return 1;
    }
    
    private static boolean validateSkillTree(char skill, Map<Character, Integer> skillMap, List<Integer> checkIdxList) {
        int turn = skillMap.get(skill);
        
        if (turn > 0) {
            int idx = checkIdxList.indexOf(turn - 1);
            if (idx == -1)
                return false;
        }
        checkIdxList.add(turn);
        
        return true;
    }
}

 

---

다른 풀이 2

프로그래머스 사이트에 있는 다른 사람의 풀이를 참고하여 위의 코드를 더욱 간결하게 작성했다.

 

수정한 부분

• skillMap을 만들 필요가 없다. 메서드를 호출할 때, skill을 매개변수로 넘겨서 선행 스킬의 순서를 찾으면 된다.
• checkIdxList도 필요가 없다. int형 변수 learningIdx를 따로 선언하여, 현재 스킬 트리에 skill에 저장된 스킬이 있는 경우, learningIdx와 같은지 검사하여 가능한 스킬 트리인지 검사하면 된다.

 

코드

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        
        int cnt = 0;
        for (String skill_tree : skill_trees) {
            cnt += countValidateSkill(skill_tree, skill);
        }
        
        return cnt;
    }
    
    private static int countValidateSkill(String skill_tree, String skillSequence) {
        int learningIdx = 0;
        
        for (int i = 0; i < skill_tree.length(); i++) {
            char skill = skill_tree.charAt(i);
            
            int idx = skillSequence.indexOf(skill);
            
            if (idx != -1) {
                if (idx == learningIdx) {
                    learningIdx++;
                }
                else return 0;
            }
        }
        
        return 1;
    }
}

 

---

다른 풀이 3

• Arrays.asList(배열) 메서드를 사용하여 String 배열 => ArrayList<String>으로 변환
• 정규 표현식을 사용하여 각 스킬 트리에서 skill인 부분을 제외한 문자열을 구한 후, skill.indexOf(문자열) 메서드를 사용하여 문자열의 위치가 0이라면, 현재 스킬 트리를 skillTrees 리스트에서 삭제한다.
• skillTrees 리스트의 크기가 가능한 스킬트리의 개수이다.

주의할 점

foreach문 대신 Iterator를 사용하는 이유는, foreach문을 사용하면 ConcurrentModificationException 예외가 발생하기 때문이다. 이 예외는 보통 리스트나 Map 등, Iterable 객체를 순회하면서 요소를 삭제하거나 변경을 할 때 발생한다. 이 예외를 방지하기 위해 Iterator를 사용하여 리스트를 순회하며 요소를 삭제한다.

참고: Java - ConcurrentModificationException 원인 및 해결 방법

 

코드

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
       
        ArrayList<String> skillTrees = new ArrayList<>(Arrays.asList(skill_trees));
        
        Iterator<String> it = skillTrees.iterator();
        
        while (it.hasNext()) {
            if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0)
                it.remove();
        }
        
        return skillTrees.size();
    }
}

 

---

1번째 풀이

2번째 풀이

3번째 풀이

정규표현식과 replaceAll()를 사용한 3번째 풀이의 코드 길이가 가장 짧지만, replaceAll()의 시간복잡도가 O(n)이므로 실행시간이 가장 오래 걸린다.

실행 시간과 코드의 가독성을 모두 고려하면, 2번째 풀이가 가장 좋은 풀이라고 생각한다.