99클럽 코테 스터디 Java 미들러 7일차 TIL - 모음 사전 : 프로그래머스 (Level 2) - DFS

1. 오늘의 문제 - 모음 사전 : 프로그래머스 (Level 2)

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

프로그래머스

 

 

2. 문제 풀이 전략

• DFS로 만들 수 있는 단어를 전부 만든다.
• 몇 번째로 만들어진 단어인지 확인한다.

3. 풀이

package io.conduktor.demos.dfsbfs.hanghaecote99.middler;

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

// 7. 프로그래머스 - 모음 사전 - 그래프 이론
public class VowelsDictionary7 {
    static List<String> list;
    static String[] vowels = {"A", "E", "I", "O", "U"};

    void dfs(String str, int len) {
        list.add(str);
        if (len == 5) return;
        for (int i = 0; i < 5; i++) {
            dfs(str + vowels[i], len + 1);
        }
    }

    public int solution(String word) {
        int answer = 0;
        list = new ArrayList<>();
        dfs("", 0);
        int size = list.size();
        for (int i = 0; i < size; i++) {
            if (list.get(i).equals(word)) {
                answer = i;
                break;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        VowelsDictionary7 dictionary = new VowelsDictionary7();
        System.out.println(dictionary.solution("A")); // 1
        System.out.println(dictionary.solution("AAAAE")); // 6
        System.out.println(dictionary.solution("AAAE")); // 10
        System.out.println(dictionary.solution("I")); // 1563
        System.out.println(dictionary.solution("EIO")); // 1189
    }
}

 

4. 다른 풀이 - 수학적 패턴 이용

구글링 해보니까 패턴을 이용해 자릿수에 따른 가중치를 계산하여 구하는 방식도 있는 듯 하다.

perplexity AI 에게 물어본 결과는 다음과 같다.

 

4 - 2. perplexity AI

이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다:

1. 각 모음의 위치에 따른 가중치 계산:
   • 첫 번째 자리: 781
   • 두 번째 자리: 156
   • 세 번째 자리: 31
   • 네 번째 자리: 6
   • 다섯 번째 자리: 1
2. 각 모음에 대한 인덱스 할당:
   • A: 0
   • E: 1
   • I: 2
   • O: 3
   • U: 4
3. 주어진 단어를 순회하면서 각 문자의 위치와 모음 인덱스를 곱한 후, 이를 모두 더합니다.
4. 최종 결과에 1을 더해 사전에서의 위치를 구합니다.

Java로 구현하면 다음과 같습니다:

class Solution {
    public int solution(String word) {
        String vowels = "AEIOU";
        int[] weights = {781, 156, 31, 6, 1};
        int answer = 0;
        
        for (int i = 0; i < word.length(); i++) {
            int index = vowels.indexOf(word.charAt(i));
            answer += index * weights[i] + 1;
        }
        
        return answer;
    }
}

이 코드의 작동 방식은 다음과 같습니다:

1. 모음 문자열과 각 위치에 대한 가중치 배열을 정의합니다.
2. 주어진 단어를 순회합니다.
3. 각 문자에 대해:
   • 해당 문자의 모음 인덱스를 찾습니다.
   • 이 인덱스에 해당 위치의 가중치를 곱합니다.
   • 결과에 1을 더합니다 (자기 자신을 포함).
4. 모든 문자에 대해 이 과정을 반복하고 결과를 누적합니다.
5. 최종 누적된 값을 반환합니다.

이 방법을 사용하면 주어진 단어가 사전에서 몇 번째 단어인지 효율적으로 계산할 수 있습니다.

 

---

perplexity AI에 따르면,

DFS로 모든 단어를 만드는 내가 푼 방식보다

수학적 패턴을 이용한 방식이 효율적으로 계산할 수 있다고 한다.

 

5. 소감

문제가 잘 안 풀린다면, 손으로 일일이 적어가면서 패턴을 찾는 것도 좋은 방법인 것 같다.