[프로그래머스][JAVA] 84512. 모음사전

💡 문제
모음사전
(https://school.programmers.co.kr/learn/courses/30/lessons/84512)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

 

---

🤓 문제 풀이

이 문제는 완전탐색을 사용하여 각 자리수의 알파벳에 대한 가중치를 계산하여, 주어진 단어의 사전 순서를 찾아냅니다. 

사전에 길이 5 이하의 모든 단어를 만들 수 있는 알파벳 모음 'A', 'E', 'I', 'O', 'U'가 사용된다고 합니다. 이 단어들을 사전 순서대로 배열했을 때, 주어진 단어 **word**가 몇 번째에 위치하는지 찾는 문제입니다. 이를 해결하기 위해 완전탐색을 사용합니다. 이를 통해 주어진 단어가 몇 번째 단어인지 효율적으로 찾을 수 있습니다.

완전탐색을 위해서는 각 위치의 문자가 알파벳 순서에 따라 얼마나 많은 단어를 생성할 수 있는지 계산해야 합니다. 각 자리에 따라 단어의 순서가 결정되므로, 특정 규칙을 찾는 것이 필요합니다.

 

🔨 접근 방법

이 접근 방식은 사전에서의 순서를 계산하는 규칙을 찾기 위한 직관적인 방법이며, 모든 가능한 단어를 생성하지 않고도 주어진 단어의 위치를 찾을 수 있습니다.

1. 알파벳 위치 값 설정:
   • 알파벳 'A', 'E', 'I', 'O', 'U'를 각 자리수에 대해 몇 번째에 위치하는지 알기 위해 배열로 설정합니다.
2. 자리수 별 가중치 계산:
   • 각 자리수의 가중치는 다음과 같습니다:
     • 첫 번째 자리수: 5^4 + 5^3 + 5^2 + 5^1 + 5^0
     • 두 번째 자리수: 5^3 + 5^2 + 5^1 + 5^0
     • 세 번째 자리수: 5^2 + 5^1 + 5^0
     • 네 번째 자리수: 5^1 + 5^0
     • 다섯 번째 자리수: 5^0
3. 단어 순서 계산:
   • 각 자리수에 해당하는 가중치와 문자의 위치 값을 곱해서 더합니다. 이는 주어진 단어가 사전에서 몇 번째에 위치하는지 계산하는 것입니다.

🔨 문제 풀이 과정

1. 알파벳 위치 값 설정:
   • char[] vowels = {'A', 'E', 'I', 'O', 'U'}; 배열을 사용하여 각 자리의 알파벳 위치를 설정합니다.
2. 자리수 별 가중치 계산:
   • int[] weight = {781, 156, 31, 6, 1}; 배열을 사용하여 각 자리수의 가중치를 설정합니다. 이 가중치는 각 자리수에 따라 얼마나 많은 단어를 생성할 수 있는지 계산한 결과입니다.
3. 단어 순서 계산:
   • 주어진 단어 **word**의 각 자리수를 순회하며, 해당 자리의 알파벳이 위치하는 인덱스를 찾고, 그 인덱스와 가중치를 곱하여 더합니다.
   • 마지막으로 각 자리수를 탐색한 후, 해당 단어를 포함하기 위해 **+1**을 합니다.

🔨 구현코드

1-실패 코드

class Solution {
    public int solution(String word) {
        // 알파벳 배열
        char[] vowels = {'A', 'E', 'I', 'O', 'U'};
        // 각 자리수의 가중치
        int[] weight = {781, 156, 31, 6, 1}; // 5^4, 5^3, 5^2, 5^1, 5^0 의 합

        int answer = 0;
        // 주어진 단어의 각 자리수에 대해 계산
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            // 문자의 위치값 계산 ('A'는 0, 'E'는 1, 'I'는 2, 'O'는 3, 'U'는 4)
            int index = 0;
            for (int j = 0; j < vowels.length; j++) {
                if (c == vowels[j]) {
                    index = j;
                    break;
                }
            }
            // 가중치와 위치값을 곱하여 순서를 계산
            answer += index * weight[i];
        }
        // 각 자리수를 탐색했으므로 그 단어를 포함하기 위해 +1
        return answer + 1;
    }
}

---

2-성공 코드

class Solution {
    public int solution(String word) {
        // 알파벳 배열
        char[] vowels = {'A', 'E', 'I', 'O', 'U'};
        // 각 자리수의 가중치
        int[] weight = {781, 156, 31, 6, 1}; // 5^4 + 5^3 + 5^2 + 5^1 + 5^0 = 781

        int answer = 0;
        // 주어진 단어의 각 자리수에 대해 계산
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            // 문자의 위치값 계산 ('A'는 0, 'E'는 1, 'I'는 2, 'O'는 3, 'U'는 4)
            int index = 0;
            for (int j = 0; j < vowels.length; j++) {
                if (c == vowels[j]) {
                    index = j;
                    break;
                }
            }
            // 가중치와 위치값을 곱하여 순서를 계산
            answer += index * weight[i];
        }
        // 각 자리수를 탐색했으므로 그 단어를 포함하기 위해 +1
        answer += word.length();
        return answer;
    }
}

---

📚 풀이 보완

실패한 원인

실패의 주요 원인은 단어의 순서를 계산할 때, 각 자리수의 위치를 고려하여 가중치를 곱하는 과정에서 최종적으로 계산된 값에 단어의 길이를 더하는 방식에서 발생했습니다. 이로 인해 결과가 올바르지 않게 나왔습니다. 원래 코드는 자리수별로 가중치를 곱한 후, 단어의 길이를 더해서 순서를 계산하는 부분에서 오류가 있었습니다.

for (int i = 0; i < word.length(); i++) {
    char c = word.charAt(i);
    int index = 0;
    for (int j = 0; j < vowels.length; j++) {
        if (c == vowels[j]) {
            index = j;
            break;
        }
    }
    answer += index * weight[i];
}
// 잘못된 부분: word.length()를 더하는 부분
return answer + word.length();

위 코드에서 answer + word.length()를 반환하는 부분이 잘못되었습니다. 단어의 순서를 계산할 때, 각 자리수의 가중치를 곱해서 더한 값에 단어의 길이를 더하는 것이 아니라, 올바른 단어의 위치를 정확히 계산한 후 반환해야 합니다.

---

코드 설명

수정된 코드는 각 자리수의 위치를 고려하여 단어의 순서를 정확히 계산한 후, 최종적으로 올바른 결과를 반환하도록 변경하였습니다.

class Solution {
    public int solution(String word) {
        // 알파벳 배열
        char[] vowels = {'A', 'E', 'I', 'O', 'U'};
        // 각 자리수의 가중치
        int[] weight = {781, 156, 31, 6, 1}; // 5^4 + 5^3 + 5^2 + 5^1 + 5^0 = 781

        int answer = 0;
        // 주어진 단어의 각 자리수에 대해 계산
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            // 문자의 위치값 계산 ('A'는 0, 'E'는 1, 'I'는 2, 'O'는 3, 'U'는 4)
            int index = 0;
            for (int j = 0; j < vowels.length; j++) {
                if (c == vowels[j]) {
                    index = j;
                    break;
                }
            }
            // 가중치와 위치값을 곱하여 순서를 계산
            answer += index * weight[i];
        }
        // 각 자리수를 탐색했으므로 그 단어를 포함하기 위해 +1
        answer += word.length();
        return answer;
    }
}

1. 위치 값 계산
   • char[] vowels = {'A', 'E', 'I', 'O', 'U'}; 배열을 사용하여 각 자리에 가능한 알파벳을 정의합니다.
   • 각 문자의 위치 값을 계산하기 위해 index를 사용합니다. 예를 들어, 'A'는 0, 'E'는 1, 'I'는 2, 'O'는 3, 'U'는 4로 설정됩니다.
2. 가중치와 위치 값 곱하기
   • **index * weight[i]**를 통해 각 자리의 가중치를 계산하여 answer에 더합니다.
   • int[] weight = {781, 156, 31, 6, 1}; 배열을 사용하여 각 자리수의 가중치를 설정합니다. 이는 다음과 같이 계산된 결과입니다:
     • 첫 번째 자리: 5^4 + 5^3 + 5^2 + 5^1 + 5^0 = 781
     • 두 번째 자리: 5^3 + 5^2 + 5^1 + 5^0 = 156
     • 세 번째 자리: 5^2 + 5^1 + 5^0 = 31
     • 네 번째 자리: 5^1 + 5^0 = 6
     • 다섯 번째 자리: 5^0 = 1
3. 정확한 순서 계산
   • 각 자리의 알파벳 위치 값을 찾아 가중치를 곱하여 더합니다.
   • **word.length()**를 더하여 각 단어의 위치를 정확히 계산합니다.
   • answer += word.length();를 통해 각 자리수의 계산이 끝난 후, 단어의 길이를 더하여 정확한 순서를 반환합니다.

테스트 케이스 설명

"AAAAE" : 순서 계산: 5번째에 위치한 E는 첫 번째 자리 'A' 5개 후에 위치하므로 6번째입니다.

"AAAE" : 순서 계산: 9번째까지의 단어 후에 위치하므로 10번째입니다.

"I" : 순서 계산: 'A', 'E', 'I'로 세 번째 알파벳이므로 1563번째입니다.

"EIO" : 순서 계산: 여러 가중치를 고려하여 1189번째 위치합니다.

---

📍 Plus+

시간 복잡도와 공간 복잡도 분석

시간 복잡도

1. 문자 위치 찾기:
   • 각 문자의 위치를 찾는 루프는 문자열의 길이(최대 5)에 대해, 알파벳 배열(길이 5)을 순회합니다.
   • 최악의 경우 시간 복잡도는 O(5 * 5) = O(25)입니다. 그러나 이는 상수 시간에 해당하므로 일반적으로 O(1)로 간주할 수 있습니다.
2. 순서 계산:
   • 각 문자 위치를 찾는 것과 함께, 가중치를 곱하여 **answer**에 더하는 작업은 문자열의 길이에 비례합니다.
   • 문자열의 길이는 최대 5이므로, 이 부분의 시간 복잡도는 O(5)입니다.

결과적으로, 시간 복잡도는 문자열의 길이에 비례하므로, 상수 시간 O(1)입니다.

공간 복잡도

1. 고정된 배열 사용:
   • vowels 배열과 weight 배열은 모두 고정된 크기(5)를 가지므로, 이는 상수 공간을 차지합니다.
   • 이 배열들은 입력 문자열의 길이와 무관하게 일정한 크기를 가지므로, 공간 복잡도에 큰 영향을 미치지 않습니다.
2. 기타 변수:
   • answer, index, **c**와 같은 변수를 사용하지만, 이는 모두 상수 공간입니다.

결과적으로, 공간 복잡도는 O(1)입니다.

요약

• 시간 복잡도: O(1)
• 공간 복잡도: O(1)