[프로그래머스] (Java) 모음사전 (완전탐색)

 

📑 1. 문제설명

---

💡 2. 접근방식

 

dfs(깊이 우선 탐색)으로 A,E,I,O,U로 조합해서 만들 수 있는 모든 단어를 리스트에 넣어 준다.

그리고 list의 사이즈만큼 반복문을 돌리면서 word랑 일치하는 단어가 들어 있는 칸의 인덱스를 반환한다. 

 

---

⭐ 3. 정답코드

import java.util.*;

class Solution {
    static List<String> list;
    static String [] words = {"A", "E", "I", "O", "U"};
    
    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;
    }
    static void dfs(String str, int len) {
        list.add(str);
        if (len==5) return;
        for (int i = 0; i < 5; i++) {
            dfs(str + words[i], len + 1);
        }
    }
}

 

 

처음에 코드 쓰면서 `answer = i + 1` 이라고 했는데 틀렸다고 오답처리가 되었다. 

인덱스는 0부터 시작인데 사람의 언어로 몇 번째 단어냐고 하면 i+1이 아닌가 생각했다.

로직 따라가면서 잘 생각 해 보니까 처음에는 빈문자열로 시작했기 때문에 0번 인덱스는 빈 스트링이다

그리고 1번 인덱스부터 A가 추가가 된다.

---

 

return과 break는 둘 다 실행 흐름을 종료하는 데 사용된다.

for루프를 종료할 때 쓰는 키워드가 `break`이다. 

반면`return`은 재귀호출을 종료한다.

즉, len이 5가 되면 재귀 호출을 종료하고 상위호출로 돌아 가야 하기 때문에 쓰는 것이다.

 

재귀호출은 쌓이는 호출이라고 생각하면 이해가 쉽다.

dfs("AAAAA", 5)가 종료되면, 쌓인 순서의 바로 아래 단계인 dfs("AAAA", 4)로 돌아간다.

 

dfs("", 0)이 실행 → dfs("A", 1) 호출
dfs("A", 1)이 실행 → dfs("AA", 2) 호출
dfs("AA", 2)이 실행 → dfs("AAA", 3) 호출.
...
dfs("AAAAA", 5) 실행 → return → 돌아감 → dfs("AAAA", 4)로 복귀. 
dfs("AAAA", 4)은 for문의 다음 반복을 진행 → dfs("AAAAE", 5) 호출.

 

 

AAAAU 이후에는?

dfs("AAAAU", 5) 종료 → 복귀 → dfs("AAAA", 4)로 돌아감.
dfs("AAAA", 4)의 for문이 모두 끝나므로 종료 → 복귀 → dfs("AAA", 3)로 돌아감.
dfs("AAA", 3)의 for문에서 다음 반복(i = 1) 실행 → dfs("AAAE", 4) 호출.

 

 

👏🏻 좋아요 많이 받은 코드

class Solution {
    public int solution(String word) {
        int answer = 0, per = 3905;
        for(String s : word.split("")) answer += "AEIOU".indexOf(s) * (per /= 5) + 1;
        return answer;
    }
}

 

수학을 아주 잘 하는 사람이 짠 코드이다.

per = 3905는 5^4 + 5^3 + 5^2 + 5^1 + 5^0의 결과이다.

 

각 문자열이 가지는 길이는 1에서 최대 5이다. 따래서 3905는 "AEIOU"로 구성된 가능한 모든 문자열의 총 개수이다.

 

1자리 문자열: "A", "E", "I", "O", "U"로 총 개수: 5개

2자리 문자열: 첫 번째 자리는 5개 문자 중 하나, 두 번째 자리는 5개 문자 중 하나. 즉, 5 * 5 = 25개
3자리 문자열: 첫 번째 자리는 5개 문자 중 하나, 두 번째 자리는 5개 문자 중 하나, 세 번째 자리는 5개 문자 중 하나. 즉, 5 * 5 * 5 = 125개
4자리 문자열: 5 * 5 * 5 * 5 = 625개.
5자리 문자열: 5 * 5 * 5 * 5 * 5 = 3125개

5 + 25 + 25 + 625 + 3125 = 3905

 

 

문자열을 문자 배열로 쪼개서 분리한다.

쪼개진 문자 하나 하나에 대해서

`AEIOU".indexOf(s)`를 하는데 문자 s가 "AEIOU" 문자열에서 몇 번째 위치에 있는지 찾는것이다.

예를 들면 A의 인덱스는 0이고 U는 맨 마지막이니까 인덱스가 4일 것이다. 

그리구 `per /= 5` 로 매 반복마다 per 값을 5로 나누어 준다.

`3905 / 5` → 781, `781 / 5` → 156, `156 / 5` → 31, `31 / 5` → 6, `6 / 5` → 1 등으로, 각각의 문자가 사전에서 차지하는 비율을 줄여가며 계산한다. 이렇게 코드 짠사람 진짜 천재인감....?

 

 

🐦 좋아요 많이 받은 코드

class Solution {
    int answer, cnt;

    public int solution(String word) {
        dfs(new StringBuilder(), word);
        return answer;
    }

    boolean dfs(StringBuilder sb, String word) {
        if (sb.toString().equals(word)) return true;
        if (sb.length() >= 5) return false;

        for (char c : "AEIOU".toCharArray()) {
            sb.append(c);
            cnt++;
            if (dfs(sb, word)) {
                answer = cnt;
                return true;
            }
            sb.deleteCharAt(sb.length() - 1);
        }
        return false;
    }
}

---

👉🏻 4. 같은 유형 문제