[Lv.2] 모음사전 : Java

프로그래머스

 

 

 

이해하기

어떻게 풀어야할지 접근조차 어려워서 풀이를 참고하였다.

[프로그래머스]모음사전 with Java

가장 잘 이해됐던 정리글! 짧은 글이었지만 접근방법을 적어주셔서 따라갈 수 있었다.

 

1. A, E, I, O, U 로 만들 수 있는 모든 단어를 Set에 저장한다.

여기서 Set을 쓴 이유를 단순히 중복 저장이 불가하기 때문이라고 생각했지만, 자세히 보니 TreeSet을 사용하셨다.

TreeSet의 특징으로는 Set과 마찬가지로 중복 저장 불가, 저장 순서 유지 안 됨이 있지만, 추가적인 장점이 존재했다.

바로 이진 탐색 트리 구조로 되어 있어 탐색이 빠르고 기본적으로 오름차순 정렬이 된다는 점이었다.

AEIOU를 사전 순으로 저장해야 하는 상황에 딱 맞는 장점이었다.

 

2. 저장해둔 Set에서 찾는 단어를 탐색한다.

 

3. answer를 리턴한다.

 

 

문제풀이

import java.util.*;

class Solution {
    Set<String> set;
    String[] arr = {"A", "E", "I", "O", "U"};

    public int solution(String word) {
        int answer = 0;
        set = new TreeSet<>();

        for (int i = 0; i < arr.length; i++) {
            makeWord(arr[i], 1);
        }

        for (String s : set) {
            answer++;

            if (s.equals(word)) {
                return answer;
            }
        }

        return answer;
    }

    public void makeWord(String base, int depth) {
        set.add(base);
        if (depth == 5) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            makeWord(base + arr[i], depth + 1);
        }
    }
}

 

가장 어려웠던 부분은 makeWord 함수였다.

하나하나 따라가보며 손으로 적어보았더니 다음과 같이 실행된다는 것을 알게 되었다.

 

A, AA, AAA, AAAA, AAAAA

AAAAE, AAAAI, AAAAO, AAAAU

AAAE, AAAEA, AAAEE, AAAEI, AAAEO, AAAEU

AAAI, AAAIA, AAAIE, AAAII, AAAIO, AAAIU

AAAO, AAAOA, AAAOE, AAAOI, AAAOO, AAAOU

AAAU, AAAUA, AAAUE, AAAUI, AAAUO, AAAUU

......

 

makeWord는 사전 순서대로 단어를 만들어주는 재귀 함수였다.

이 부분만 구현한다면 다음 풀이는 쉬웠다.

하지만 재귀는 언제나 어려워...😢

 

 

 

재귀 파트 들어오자마자 현저히 떨어지는 성공률...^^

재귀, dfs, bfs 파트가 내 약점인 것 같다.

어려울수록 많이 풀어봐야한다는 것을 알지만 오히려 더 풀기 싫은 마음🥹