99클럽 코테 스터디 7일차 TIL

프로그래머스 - 모음 사전

단어가 만들어지는 규칙이 이해가 안됐지만 계속 보다보니 dfs 순서로 만들어지고 있다는 것을 알게 되었다.

풀이

• 주어진 A, E, I, O, U 사용하여 dfs 순서대로 단어를 생성한다. 
• 생성된 단어들을 dictionary라는 리스트 자료구조에 저장한다.
• 생성된 단어의 길이가 5를 넘는다면 상단에서 Early return으로 스택 프레임에 쌓인 함수를 종료시킨다.

단어 생성 재귀 함수

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static final String[] ALPHABETS = {"A", "E", "I", "O", "U"};
    private static final List<String> DICTIONARY = new ArrayList<>();

    public int solution(String word) {
        int answer = 0;
        generateWords("");

        return answer;
    }
    
    // 단어 생성 재귀 함수
    private void generateWords(String word) {
        if (word.length() > 5) return;
        DICTIONARY.add(word);

        for (int i = 0; i < ALPHABETS.length; i++) {
            generateWords(word + ALPHABETS[i]);
        }
    }
}

재귀 함수를 통해 규칙에 맞게 모든 단어가 dictionary에 담겼다.

dictionary를 순차적으로 돌면서 주어진 word와 같은 경우, 해당 인덱스를 반환한다.

public int solution(String word) {
    int answer = 0;
    
    generateWords("");
    
    for (int i = 0; i < DICTIONARY.size(); i++) {
        if (word.equals(DICTIONARY.get(i))) {
            answer = i;
            break;
        }
    }
    return answer;
}

generateWords 함수에 빈 값을 넣었기 때문에 dictionary의 0번째는 ""로 들어가고 실제 단어는 1번부터 시작된다.

 

이대로 끝낼 수 있지만 dictionary 반복문을 줄일 수 있을 것 같다.

List의 내부 메서드인 indexOf를 사용하여 반복문 구현 필요없이 해당 문자열의 인덱스를 바로 반환하도록 했다.

public int solution(String word) {
    generateWords("");
    return DICTIONARY.indexOf(word);
}

최종 코드

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static final String[] ALPHABETS = {"A", "E", "I", "O", "U"};
    private static final List<String> DICTIONARY = new ArrayList<>();

    public int solution(String word) {
        generateWords("");
        return DICTIONARY.indexOf(word);
    }
    
    private void generateWords(String word) {
        if (word.length() > 5) return;
        DICTIONARY.add(word);

        for (int i = 0; i < ALPHABETS.length; i++) {
            generateWords(word + ALPHABETS[i]);
        }
    }
}

---

프로그래머스 - 모음 사전

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