프로그래머스 - 49993번: 스킬트리 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        for(String s : skill_trees) {
            Map <Character, Integer> map = new HashMap<>();
            for(int i = 0; i < s.length(); i++)
                map.put(s.charAt(i), i + 1);

            Stack <Integer> stack = new Stack<>();
            for(int i = 0; i < skill.length(); i++) {
                if(map.containsKey(skill.charAt(i)))
                    stack.push(map.get(skill.charAt(i)));
                else
                    stack.push(0);
            }
            while(!stack.isEmpty() && stack.peek() == 0)
                stack.pop();
            int n = 0;
            if(!stack.isEmpty())
                n = stack.pop();

            while(!stack.isEmpty()) {
                if(n <= stack.peek() || stack.peek() == 0)
                    break;
                else
                    n = stack.pop();
            }
            if(stack.isEmpty())
                answer++;
        }
        return answer;
    }
}

2. 설명

int answer = 0;
for(String s : skill_trees) {
    Map <Character, Integer> map = new HashMap<>();
    for(int i = 0; i < s.length(); i++)
        map.put(s.charAt(i), i + 1);

for-each문을 통해서 skill_trees를 하나씩 접근합니다. 그리고 문자열 s에서의 각 문자에 대한 인덱스 값을 HashMap에 저장합니다.

    Stack <Integer> stack = new Stack<>();
    for(int i = 0; i < skill.length(); i++) {
        if(map.containsKey(skill.charAt(i)))
            stack.push(map.get(skill.charAt(i)));
        else
            stack.push(0);
    }

반복문을 통해서 스택에 skill의 각 문자가 skill_trees의 인덱스 값을 HashMap의 값을 이용하여 push 합니다. 만약 HashMap에 존재하지 않으면 0을 push 해줍니다.

    while(!stack.isEmpty() && stack.peek() == 0)
        stack.pop();
    int n = 0;
    if(!stack.isEmpty())
        n = stack.pop();

스택이 비어있지 않고 stack의 peek 값이 0이라면 pop을 하여 0을 제거합니다. 그리고 만약 stack이 비어있지 않으면 n에 stack값을 pop 해줍니다.

    while(!stack.isEmpty()) {
        if(n <= stack.peek() || stack.peek() == 0)
            break;
        else
            n = stack.pop();
    }
    if(stack.isEmpty())
        answer++;

스택이 비어질 때까지 반복해 주는데 만약 스택의 peek 값이 n보다 크거나 stack의 값이 0이라면 반복문을 종료합니다. 그 이유는 스킬 트리가 지켜지지 않았다는 것을 의미하기 때문입니다.

만약 아니라면 n에 stack의 값을 pop 해주며 진행됩니다. 그리고 이 모든 과정이 마치고 스택이 비어있다면 answer를 추가해 줍니다.

3. 정리

• 스택이 비어있는지 확인만 잘한다면 쉽게 해결 가능하다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges