프로그래머스 - 모음사전

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

프로그래머스

 

재귀호출을 활용하여 풀 수 있는 문제이다.

 

요구사항

1. "A","E","I","O","U" 를 이용해서 만들 수 있는 5자리 이하 문장을 만들어야 한다.

2. 주어진 문자열이 사전순으로 몇번째에 위치 하는지를 구해야 한다.

 

우선 사전순으로 들어가야 한다면 다음과 같은 순서로 들어가야 할것이다.

A

AA

AAA

AAAA

AAAAA

AAAAE

AAAAI

AAAAO

.

.

.

AAAEA

.

.

.

E

EA

EAA

.

.

.

 

이를 구현하기 위해 리스트를 생성하고 재귀호출 하면서 만들어지는 문자열을 list에 삽입해준다.

 

단, 문자열의 길이가 5를 넘어가면 더이상 문자를 뒤에 삽입하면 안되므로 return해준다.

public static void insert(String[] ch,String str,int depth){
        list.add(str);
        if(depth==5){
            return;
        }
        for(int i=0; i<ch.length; i++){
            insert(ch,str+ch[i],depth+1);
        }
    }

 

 

그 후 리스트를 순회하면서 주어진 문자열과 같은 문자열을 찾아서 위치를 반환 해주면 된다.

for(int i=0; i<list.size(); i++){
            if(list.get(i).equals(word)){
                answer=i;
            }
        }

 

 

<전체 코드>

import java.util.*;

class Solution {
    public static int answer;
    public static List<String> list;
    public int solution(String word) {
        list = new ArrayList<>();
        String[] ch = new String[]{"A","E","I","O","U"};
        insert(ch,"",0);
      
        for(int i=0; i<list.size(); i++){
            if(list.get(i).equals(word)){
                answer=i;
            }
        }
        
        return answer;
    }
    
    public static void insert(String[] ch,String str,int depth){
        list.add(str);
        if(depth==5){
            return;
        }
        for(int i=0; i<ch.length; i++){
            insert(ch,str+ch[i],depth+1);
        }
    }
}

 

 

---

 

2025년 03월 23일

 

다시 풀어보니 더 간결한 코드로 문제를 해결할 수 있었다.

 

<정답 코드>

import java.util.*;

class Solution {
    static int answer =0;
    static int n=0;
    public int solution(String word) {
       char[] arr = {'A','E','I','O','U'};

        dfs(word,"",arr);
        return n;
    }
    public static void dfs(String word, String str,char[] arr){
        if(word.equals(str)){ //원하는 word에 도착한 경우에 answer를 n에 저장
            n=answer;
            return;
        }
        if(str.length() ==5){ //문자열 길이가 5이상이면 더이상 문자를 추가할 수 없다.
            return;
        }
        for(int i=0; i<5; i++){
            answer++;
            dfs(word,str+arr[i],arr);
        }
        return;
    }
}