문제
https://school.programmers.co.kr/learn/courses/30/lessons/84512
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
접근 방식
모음 5개(A, E, I, O, U)를 사용해서 만들 수 있는 단어의 길이의 종류는 5개이다(1글자 ~ 5글자)
글자 수단어 개수
1 | 5^1 = 5 |
2 | 5^2 = 25 |
3 | 5^3 = 125 |
4 | 5^4 = 625 |
5 | 5^5 = 3125 |
합계 | 3905 |
모든 경우의 수를 다 만들어도 4000개 정도이기 때문에 모든 경우를 다 확인하는 완전 탐색으로 풀어도 가능하다.
재귀함수를 통해 가능한 모든 단어를 다 만들고 구하고자 하는 word가 몇 번째에 있는지 확인하면 된다.
풀이
재귀로 단어 만들기
만든 단어를 넣어줄 리스트, 모음이 담긴 문자열 배열을 전역변수로 만들어 준다.
String[] vowels = {"A", "E", "I", "O", "U"};
ArrayList<String> list = new ArrayList<>();
결과는 1부터 시작해야 하기 때문에 list에 넣을 때도 0번째 인덱스에는 아무 것도 들어가지 않은 값을 하나 넣고 단어는 1번 인덱스부터 시작할 수 있도록 했다. 재귀 첫 시작에 단어를 리스트에 넣는다.
모음 배열을 돌면서 함수를 재귀 호출하면서 문자열에 모음을 하나씩 붙여 만든다.
단어는 최대 길이가 5이기 때문에 호출의 깊이가 5가 되면 return 하도록 한다.
void findWord(String str, String target, int depth){
list.add(str);
if(depth == 5) return;
for(int i=0; i<vowels.length; i++){
findWord(str + vowels[i], target, depth+1);
}
}
word를 list에서 찾기
for문을 돌며 선형탐색으로 list에서 word를 찾고 찾으면 그 때의 i를 return 한다.
for(int i=0; i<list.size(); i++){
if(word.equals(list.get(i))){
answer = i;
}
}
전체 코드
import java.util.*;
class Solution {
String[] vowels = {"A", "E", "I", "O", "U"};
ArrayList<String> list = new ArrayList<>();
public int solution(String word) {
int answer = 0;
findWord("", word, 0);
for(int i=0; i<list.size(); i++){
if(word.equals(list.get(i))){
answer = i;
}
}
return answer;
}
void findWord(String str, String target, int depth){
list.add(str);
if(depth == 5) return;
for(int i=0; i<vowels.length; i++){
findWord(str + vowels[i], target, depth+1);
}
}
}
'Programming > Programmers' 카테고리의 다른 글
[프로그래머스] Lv2. 전력망을 둘로 나누기(Java) (0) | 2023.09.25 |
---|---|
[프로그래머스] Lv2. 소수 찾기(Java) (0) | 2023.09.22 |
[프로그래머스] Lv2. 단어 변환(Java) (0) | 2023.09.22 |
[프로그래머스] Lv2. 멀쩡한 사각형(Java) (0) | 2023.07.27 |
[프로그래머스] Lv2. 숫자 카드 나누기(Java) (0) | 2023.07.27 |