[알고리즘] 프로그래머스 스킬트리 -서머코딩/윈터코딩(~2018)

https://programmers.co.kr/learn/courses/30/lessons/49993?language=java

프로그래머스

프로그래머스에서 스킬트리 라는 문제를 풀어보았습니다. 유형은 안적혀있네요. 이걸 뭔 문제라하지 흠..

서머코딩/윈터코딩(~2018) 라고만 적혀있습니다.

스킬트리 라는 제목에 끌려 풀게됬습니다.

 

1. 스킬트리 인가 체크

2. 스킬트리의 선마 스킬을 배웠는가 체크

 

[좀더 자세히 설명 2020.05.08 코드 변수명 및 주석 업데이트] => 이전 코드보는데 좀 알아보기 힘들어서 변수명과 주석을 조금 추가했습니다. 그래도 보기가 좀 어렵네여. 지금 다시봐도 좀 이상하게 푼 것 같습니다. 햇갈리게 풀은듯.. 다시 풀만한 문제는 아니므로 다시풀진 않겠습니다.

풀이는 다음과 같습니다.

class Solution {
    public int solution(String gameSkillTree, String[] skill_trees) { //선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees
        int answer = 0;
        int prevGameSkillIndex = -1;
        for (int i = 0; i < skill_trees.length; i++) { //유저스킬트리 반복
            prevGameSkillIndex = -1; // 배운 게임스킬트리 스킬 인덱스
            String userSkillTree = skill_trees[i]; //유저 스킬트리
            for (int j = 0; j < gameSkillTree.length(); j++) { // 게임 스킬트리의 스킬 하나씩 반복 (게임 스킬을 유저 스킬트리와 비교)
                String gameSkill = String.valueOf(gameSkillTree.charAt(j));
                if (userSkillTree.contains(gameSkill)) { // 유저 스킬트리에 게임 스킬이 있는 경우
                    if (userSkillTree.indexOf(gameSkill) > prevGameSkillIndex) { // 유저스킬트리에 게임스킬 인덱스가 이전 게임스킬트리 인덱스보다 뒤에있는거야함
                        if (j > 0) { // 두번째 이상의 게임스킬인 경우
                            String prevSkill = String.valueOf(gameSkillTree.charAt(j - 1)); // 이전에 배운 게임스킬
                            if (userSkillTree.contains(prevSkill)) { // 이전 스킬을 유저가 배웠는지 배웠다면 유저스킬트리의 해당 게임스킬 위치를 저장 (이전에 배운 prevGameSkillIndex 보다 클거임)
                                prevGameSkillIndex = userSkillTree.indexOf(gameSkill); 
                            } else { // 이전스킬 안배웠으면 잘못된거임 break
                                break;
                            }
                        } else { //첫번째 게임 스킬인 경우 유저스킬트리의 해당 게임스킬 위치를 저장
                            prevGameSkillIndex = userSkillTree.indexOf(gameSkill);
                        }
                    } else {
                        break;
                    }
                }
                //마지막 스킬 검사인 경우
                if (j == gameSkillTree.length() - 1) {
                    answer++;
                }
            }
        }
        return answer;
    }
}

 

 

 

 

P.S

요즘 게을려져서 알고리즘을 많이 쉬었습니다.

BFS, DFS 복습도 하고 다른 응용 유형도 풀어볼려고합니다. (백트랙킹, 동적계획법, 최단경로 ....)

게을러지지 말고 일주일에 적어도 세문제는 풀도록 노력해야겠습니다.