프로그래머스 - 스킬트리

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

프로그래머스

 

 

 

 

 

 

문제

• 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때
• 가능한 스킬트리 개수를 return

 

제한사항

• 선행 스킬 순서 skill의 길이는 1 이상 26 이하
• skill_trees는 길이 1 이상 20 이하인 배열
• skill_trees의 원소는 길이가 2 이상 26 이하인 문자열

 

입출력 예시

skill	skill_trees	return
"CBD"	{"BACDE", "CBADF", "AECB", "BDA"}	2

 

 

 

 

 

풀이

• 스킬트리가 가능한지 선행 스킬 순서에 맞는지 판단하기
  • skill에 있는 문자와 일치한다면, 그 스킬의 인덱스를 저장
  • 다음에 일치하는 문자가 저장한 인덱스보다 작으면(선행 스킬 순서에 맞지 않음) => 불가능
  • 저장한 인덱스보다 크면(순서에 맞음) => 스킬 순서 증감

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0; //정답 : 가능한 스킬트리 개수
        
        for(int i = 0; i < skill_trees.length; i++) {
            if(isPossible(skill, skill_trees[i])) { //스킬트리 가능한지
                answer++;
            }
        }
        
        return answer;
    }
    
    public boolean isPossible(String skill, String skill_tree) {
        int order = 0; //스킬의 순서 저장
        
        for(int i = 0; i < skill_tree.length(); i++) {
            int idx = skill.indexOf(skill_tree.charAt(i)); //해당 스킬의 순서 가져옴
            
            if(idx == -1) continue;
            
            if(order < idx) { //선행되지 않으면
                return false; //불가능
            } else { //선행되었으면
                order++; //스킬 순서 증감
            }      
        }
        
        return true;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• int indexOf(Object o)
  • 리스트에 있으면 해당 인덱스 반환, 리스트에 없으면 -1 반환