[프로그래머스 lv1] 옹알이 (2)

문제 보기

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

프로그래머스

 

 

 

문제 해결

map과 stack 자료구조를 이용해서 문제를 해결하였다.

1. "aya", "ye", "woo", "ma"를 key로 정하여 map 자료구조에 삽입

String[] word_list = {"aya","ye","woo","ma"};
Map<String, Integer> map = new HashMap<>();
for (String word : word_list) {
    map.put(word, 1);
}

 

2. 단어 하나씩 탐색해서 발음할 수 있는 단어들은 stack에 삽입하고 그 단어의 길이만큼 길이를 제거한다.

연속해서 같은 발음은 하지 못하니까 stack에 원소가 있을 경우, stack에 가장 최근에 들어간 단어와 현재 단어가 일치한다면 stack에 넣지 못하도록 설정하였다.

for (String word : babbling) {
    String str = "";
    Stack<String> stack = new Stack<>();
    int length = word.length();
    for (int i=0; i<word.length(); i++) {
        str += word.substring(i, i+1);
        if (map.containsKey(str)) {
            if ((stack.size() == 0) || (stack.size() >= 1 && !str.equals(stack.get(stack.size()-1)))) {
                stack.push(str);
                length -= str.length();
                str = "";                        
            }
        }
    }

 

3. 모든 길이가 없어졌으면 (길이가 0이면) 발음할 수 있는 단어로 가정함.

if (length == 0) {
    answer++;
}

 

 

 

소스 코드 (최종 답안)

// https://school.programmers.co.kr/learn/courses/30/lessons/133499
import java.util.*;
class Solution {
    public int solution(String[] babbling) {
        int answer = 0;
        
        String[] word_list = {"aya","ye","woo","ma"};
        Map<String, Integer> map = new HashMap<>();
        for (String word : word_list) {
            map.put(word, 1);
        }
        
        for (String word : babbling) {
            String str = "";
            Stack<String> stack = new Stack<>();
            int length = word.length();
            for (int i=0; i<word.length(); i++) {
                str += word.substring(i, i+1);
                if (map.containsKey(str)) {
                    if ((stack.size() == 0) || (stack.size() >= 1 && !str.equals(stack.get(stack.size()-1)))) {
                        stack.push(str);
                        length -= str.length();
                        str = "";                        
                    }
                }
            }
            if (length == 0) {
                answer++;
            }
        }
        
        
        return answer;
    }
}