[프로그래머스] 스킬트리 (구현_Java)

위상정렬인가,

아니면 그냥 구현인가

계속 고민하다가 구현으로 푼 문제!

 

사실 위상정렬도 복습하긴 해야 한다.

 

---

문제

 

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

프로그래머스

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 구현

문자열을 배열로 변경하고, 그 배열을 리스트로 바꿔서 리스트에 있는 메서드를 사용하는 것이 관건이었다.

 

풀이 과정

1.

선행과정을 String 문자열에서 String 리스트로 변경한다.

 

2.유저들이 만든 스킬트리 배열 값을 String리스트로 변환한다.그리고 선행과정 순서를 담을 배열 seq를 생성한다.그리고 유저들이 만든 스킬트리 리스트에서 선행과정 과목들이 각각 몇 번째에 있는지 seq배열에 저장한다.

 

3.유저들이 만든 스킬트리 리스트를 거꾸로 순회한다.만약 현재 유저들이 만든 스킬트리 값이 선행과정에 있는 과목이라면 flag를 true로 변경한다.이미 선행과정에 필요한 과목이 seq배열에 있는데, 현재 과목이 리스트에 없다면 선행이 될 수 없으므로 isCorrect를 flase로 변경한다.그리고 현재 값이 그 전의 값보다 작다면, 순서가 맞지 않는 것이므로 isCorrect를 false로 변경한다.

 

4.반복문 종료 후 isCorrect가 true라면, answer를 하나 증가한다.

 

5.answer를 리턴한다.

 

---

코드

 

import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        String[] charSkill = skill.split("");
        
        for(int i=0; i<skill_trees.length; i++){
            
            //리스트로 변경
            String[] str = skill_trees[i].split("");    
            List<String> treeList = new ArrayList(Arrays.asList(str));
            
            //리스트에서 과목이 몇번째에 있는지 저장
            int[] seq = new int[charSkill.length];
            for(int j=0; j<seq.length; j++){
                seq[j] = treeList.indexOf(charSkill[j]);    
            }
            
            //선행스킬이 맞는지 확인
            boolean flag = false;
            boolean isCorrect = true;
            for(int j=seq.length-1; j>=0; j--){
                if(seq[j]!=-1) flag=true;   //현재 선행과목이 리스트에 있다면        
                if(flag && seq[j]==-1) isCorrect = false;               //후행과목이 리스트에 있는데, 선행과목이 없을 경우 
                if(j!=0 && flag && seq[j]<seq[j-1]) isCorrect = false;  //선행과목보다 후행과목이 더 앞에 있을 경우
            }
            
            if(isCorrect) answer++;
            
        }
        
        return answer;
    }
}

 

 

(❁´◡`❁)

끝!