Menu

Subscribe

[JAVA/프로그래머스] Summer/Winter Coding(~2018) : 스킬트리

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. skill의 각 문자를 K, 인덱스를 V로 하여 해시맵에 넣는다.
  2. 해시맵을 이용해 스킬트리의 문자가 스킬이라면 value(인덱스)를 확인하여 순서대로 진행되는지 본다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        HashMap<Character, Integer> map=new HashMap<>();
        for(int i=0;i<skill.length();i++){ // 해시맵에 스킬과 인덱스 저장
            map.put(skill.charAt(i), i);
        }
        
        for(String s:skill_trees){
            int n=s.length();
            int idx=0; // 학습해야 할 스킬 인덱스
            boolean flag=true;
            for(int i=0;i<n;i++){
                int val=map.getOrDefault(s.charAt(i), -1);
                if(val==-1) continue; // 해당 문자가 스킬이 아니면 패스
                // 스킬일 경우
                if(idx==val) idx++; // 학습할 스킬이라면 학습
                else { // 아니라면 잘못된 문자열이므로 break
                    flag=false;
                    break;
                }
                
            }
            if(flag) answer++;
        }
        return answer;
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 해시맵에 스킬의 순서를 저장한다
    • K: 스킬 문자, V: 인덱스(스킬 순서)
    • 인덱스 순서대로 스킬이 진행된다는 뜻이다.
    • 스킬 문자를 숫자로 치환해줬다고 생각하면 쉽다.
  2. 스킬트리의 문자를 하나씩 확인한다
    • idx는 배워야 할 스킬 단어를 뜻한다.
    • val은 map에서 i번째 문자열의 인덱스를 가져온다. map에 없다면 -1을 반환한다.
    • i번째 문자가 map에 없다면(-1) 배울 수 있는 문자이므로 continue
    • map에 존재한다면 idx를 체크하여 스킬 순서에 맞는지 확인해야 한다.
    • idx==val이면 스킬 학습이 가능하므로 idx++하여 다음 배워야 할 스킬을 가리키도록 한다.
    • idx!=val이라면 idx 뒤의 문자를 가지고 온 것이므로 flag를 통해 잘못된 스킬트리임을 표시하고 break한다.
    • for문 탈출 후 flag가 true여야 가능한 스킬트리라는 뜻이므로 answer++한다.

👏 해결 완료!