[프로그래머스/자바] 스킬트리 - Java

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

프로그래머스

 

 

import java.util.*;
 
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        for (String skillTree : skill_trees) {
            if (isValidSkillTree(skill, skillTree)) {
                answer++;
            }
        }
        
        return answer;
    }
 
    private boolean isValidSkillTree(String skill, String skillTree) {
        int[] skillOrder = new int[26]; // 스킬 순서를 저장할 배열
        Arrays.fill(skillOrder, 26); // 초기값은 26으로 설정
        
        for (int i = 0; i < skill.length(); i++) {
            skillOrder[skill.charAt(i) - 'A'] = i; // 스킬 순서를 저장
        }
        
        int lastSkill = -1; // 마지막으로 배운 스킬 인덱스를 저장할 변수, 초기값은 -1
        for (char c : skillTree.toCharArray()) {
            int currentSkill = skillOrder[c - 'A']; // 현재 스킬의 순서를 찾음
            
            // 현재 스킬이 선행 스킬이고, 순서가 마지막으로 배운 스킬 인덱스보다 1보다 크면 false 반환
            if (currentSkill != 26 && currentSkill > lastSkill + 1) {
                return false;
            }
            
            lastSkill = Math.max(lastSkill, currentSkill); // 마지막으로 배운 스킬 인덱스 업데이트
        }
        
        return true;
    }
}
 
 
 
 
 

초기 코드는 일부 테스트 케이스에서 오류가 났다. 아래는 모든 테스트 케이스를 통과한 코드이다.

 

 

import java.util.*;
 
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        for (String skillTree : skill_trees) {
            if (isValidSkillTree(skill, skillTree)) {
                answer++;
            }
        }
        
        return answer;
    }
 
    private boolean isValidSkillTree(String skill, String skillTree) {
        int[] skillOrder = new int[26]; // 스킬 순서를 저장할 배열
        Arrays.fill(skillOrder, -1); // 초기값은 -1로 설정
        
        for (int i = 0; i < skill.length(); i++) {
            skillOrder[skill.charAt(i) - 'A'] = i; // 스킬 순서를 저장
        }
        
        int lastSkill = -1; // 마지막으로 배운 스킬 인덱스를 저장할 변수, 초기값은 -1
        for (char c : skillTree.toCharArray()) {
            int currentSkill = skillOrder[c - 'A']; // 현재 스킬의 순서를 찾음
            
            // 현재 스킬이 선행 스킬이고, 순서가 마지막으로 배운 스킬 인덱스보다 1보다 크면 false 반환
            if (currentSkill != -1 && currentSkill > lastSkill + 1) {
                return false;
            }
            
            if (currentSkill != -1) {
                lastSkill = currentSkill; // 마지막으로 배운 스킬 인덱스 업데이트
            }
        }
        
        return true;
    }
}
 

 

이전 코드에서는 HashMap을 사용하여 선행 스킬 순서를 저장했으나, int[] 배열을 사용해 가독성과 효율성을 높였다.

또한, 스킬 순서가 올바를 때만 lastSkill 변수를 업데이트 해주도록 로직을 변경해 문제를 해결하였음.