[프로그래머스 level2] 스킬트리

문제

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

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

 

풀이

1) 선이수과목 리스트를 만들었다. 선행스킬리스트가 CBD라고 주어졌으면 과목 B의 선이수스킬은 C이고, D의 선이수 스킬은 B가 된다. 

이런 식으로 리스트를 만들었고, 선이수스킬이 없는 경우에는 ' ' 을 넣었다. 리스트의 인덱스는 알파벳 대문자의 아스키 코드를 이용했다.

preSkillList = new char[26];
Arrays.fill(preSkillList,' ');

for(int index = 0 ; index<skill.length(); index++){
    char currentSkill = skill.charAt(index);
    if(index ==0){
        preSkillList[currentSkill-65] = ' ';
    }
    else{
        char prevSkill = skill.charAt(index-1);
        preSkillList[currentSkill-65]= prevSkill;
    }
}
   

 위와 같이 구현하면 CBD의 선행스킬리스트는 아래와 같다

 [ , C,  , B,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ] 

 

2) 이제 가능한 스킬트리인지 아닌지를 검사하려는 문자열에 대해 모든 경우를 검사한다. AEDCB 인 경우 for문으로 B부터 E 까지 순회하면서 현재 스킬을 기준으로 이전에 선이수스킬이 있는지 여부를 검사하면 된다. 

 

 

이때 플래그를 설정한다. for문으로 B부터 E 까지 순회할때 검사하려는 스킬 각각에 대해서 선수스킬이 있는지 여부를 확인하기 위한 플래그이다. 검사하려는 문자열에 대해 순회를 끝냈을 때 ,flag가 true 이면 count를 하나 증가 시킨다. 

 

 

check

- 처음 문제를 풀때는 flag때문에 틀렸었다. 

    public static void checkValidation(String[] list){
        for(int index = 0 ; index<list.length; index++){
            String toBeChecked = list[index];

            boolean isValid = false;
            for(int  i= 0 ; i<toBeChecked.length(); i++){
                char currentSkill = toBeChecked.charAt(i);
                char preSkill = preSkillList[currentSkill-65];

                if(preSkill ==' '){
                    continue;
                }
                else{
                   for(int j = i-1; j>=0; j--){
                       if(toBeChecked.charAt(j) == preSkill){
                           isValid = true;
                       }
                   }

                   if(!isValid) break;
                }
            }

            if(isValid) ++count;
        }
    }

위의 경우 검사해야할 문자열에서 모든 문자가 선이수과목이 없는 경우 (XYZ) isValid 가 false여서 count가 되지 않는다. 플래그(isValid)를 무엇으로 초기화 해야하는지, 어디서 초기화를 해야하는지는 플래그의 역할을 생각해봐야 한다. 이 부분은 좀 더 연습이 필요

 

코드

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;

class Solution {
    public static char[] preSkillList;
    public static int count = 0;
    
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        preSkillList = new char[26];
        Arrays.fill(preSkillList,' ');

        for(int index = 0 ; index<skill.length(); index++){
            char currentSkill = skill.charAt(index);
            if(index ==0){
                preSkillList[currentSkill-65] = ' ';
            }
            else{
                char prevSkill = skill.charAt(index-1);
                preSkillList[currentSkill-65]= prevSkill;
            }
        }
        
        checkValidation(skill_trees);
        answer  = count;
        
        return answer;
    }
    public static void checkValidation(String[] list){
        for(int index = 0 ; index<list.length; index++){
            String toBeChecked = list[index];

            boolean isValid = false;
            for(int  i= 0 ; i<toBeChecked.length(); i++){
                char currentSkill = toBeChecked.charAt(i);
                char preSkill = preSkillList[currentSkill-65];

                if(preSkill ==' '){
                    continue;
                }
                else{
                   for(int j = i-1; j>=0; j--){
                       if(toBeChecked.charAt(j) == preSkill){
                           isValid = true;
                       }
                   }

                   if(!isValid) break;
                }
            }

            if(isValid) ++count;
        }
    }
}

 

다른 풀이

- 스터디친구의 다른 풀이가 더 효율적이었다. 선행스킬순서가 BCD이면, 검사해야할 문자열에서 BCD가 있는 인덱스의 순서가 B의 인덱스<= C의 인덱스 <= D의 인덱스를 만족해야한다 . B가 C보다 앞서 나와야 하고, C는 D보다 앞서나와야 하기 때문이다. 즉 BACDE의 경우 BCD가 있는 인덱스는 023이므로 내림차순이 아니다.  CBADF의경우 1 0 3 이므로 유효하지 않은 스킬트리이다. 

 

 

-처음에 인덱스의 초기값을 -1로 했더니 실패했다. 100으로 초기화를 해야하는 이유에 대해서는 아직 한문장으로 정리하기가 어렵다. (<= <= 의 순서이기 때문?)

 

-경우의 수를 생각해보기 스킬트리가 CBD일때  ooo oox oxo ... 이런식으로 체크해야하는 문자열에 CBD가 있는 있는경우/ 없는경우를 생각하기 . 그럼 어떻게 초기화를 해야하는지 대충 그려진다. 

public static void checkValidation(String[] list){
        for(int index = 0 ; index<list.length; index++){
            String toBeChecked = list[index];               //들을 수 있는지 확인하려고 하는 과목리스트

            int[] skillsIndex = new int[skills.length];     
            for(int i = 0 ; i<skills.length; i++){
                char skill = skills[i];
                skillsIndex[i] = 100;

                for(int  j = 0 ; j<toBeChecked.length(); j++){
                    if(toBeChecked.charAt(j) == skill){
                        skillsIndex[i] = j;
                    }
                }
            }


            //skillsIndex가 <= <= 를 만족하는치 체크
            boolean isValid = true;
            for(int i = 1 ; i<skillsIndex.length; i++){
                if(skillsIndex[i]<skillsIndex[i-1]){
                    isValid = false;
                }
            }

            if(isValid) count++;
        }
    }

 

 

comment

 

-깊이, 오래 생각하는 연습