์ฌ์ ์ ์ํ๋ฒณ ๋ชจ์ 'A', 'E', 'I', 'O', 'U'๋ง์ ์ฌ์ฉํ์ฌ ๋ง๋ค ์ ์๋, ๊ธธ์ด 5 ์ดํ์ ๋ชจ๋ ๋จ์ด๊ฐ ์๋ก๋์ด ์์ต๋๋ค. ์ฌ์ ์์ ์ฒซ ๋ฒ์งธ ๋จ์ด๋ "A"์ด๊ณ , ๊ทธ๋ค์์ "AA"์ด๋ฉฐ, ๋ง์ง๋ง ๋จ์ด๋ "UUUUU"์ ๋๋ค.
๋จ์ด ํ๋ word๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ด ๋จ์ด๊ฐ ์ฌ์ ์์ ๋ช ๋ฒ์งธ ๋จ์ด์ธ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
word | result |
---|---|
"AAAAE" | 6 |
"AAAE" | 10 |
"I" | 1563 |
"EIO" | 1189 |
์ฌ์ ์์ ์ฒซ ๋ฒ์งธ ๋จ์ด๋ "A"์ด๊ณ , ๊ทธ๋ค์์ "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... ์ ๊ฐ์ต๋๋ค. "AAAAE"๋ ์ฌ์ ์์ 6๋ฒ์งธ ๋จ์ด์ ๋๋ค.
"AAAE"๋ "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"์ ๋ค์์ธ 10๋ฒ์งธ ๋จ์ด์ ๋๋ค.
"I"๋ 1563๋ฒ์งธ ๋จ์ด์ ๋๋ค.
"EIO"๋ 1189๋ฒ์งธ ๋จ์ด์ ๋๋ค.
์ด ๋ฌธ์ ๋ "A", "E", "I", "O", "U" ์ ๋ชจ๋ ๊ฐ๋ฅํ ์กฐํฉ์ ์์ฑํ๊ณ , ์ฃผ์ด์ง ๋จ์ด์ ์ธ๋ฑ์ค๋ฅผ ์ฐพ์๋ด๋ฉด ๋๋ ๋ฌธ์ ์ด๋ค.
๊ทธ๋์ ๋๋ DFS๋ก ๋ชจ๋ ๋ชจ์ ์กฐํฉ์ ์์ฑํ๋ฉฐ, ๊ฐ ์กฐํฉ์ด ์ฃผ์ด์ง ๋จ์ด์ ์ผ์นํ๋ ์ง ํ์ธํด๋๊ฐ๋๋ก ๊ตฌํ์ ํ์๋ค.
class Solution {
public String[] dict; // ๋ชจ์์ ์ ์ฅํ๋ ๋ฌธ์์ด ๋ฐฐ์ด
public int cnt = 0; // ํ์ฌ๊น์ง ์์ฑ๋ ๋ฌธ์์ด์ ์ธ๋ฑ์ค๋ฅผ ์ ์ฅํ๋ ๋ณ์
public int answer = 0; // ์ฃผ์ด์ง ๋จ์ด์ ์ธ๋ฑ์ค๋ฅผ ์ ์ฅํ๋ ๋ณ์
public int solution(String word) {
dict = "AEIOU".split(""); // ๋ชจ์ ๋ฌธ์์ด ์ ์ฅ
dfs("", word); // DFS ํธ์ถ
return answer;
}
public void dfs(String cur, String word){
// ํ์ฌ ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ 5๊ฑฐ๋ ํ์ฌ ๋ฌธ์์ด์ด word์ ๊ฐ์ผ๋ฉด
if(cur.length() == 5 || cur.equals(word)){
if(cur.equals(word)){
answer = cnt; // ํ์ฌ ์ธ๋ฑ์ค ์ ์ฅ
}
return; // ๋ ์ด์ ํ์ํ ํ์๊ฐ ์์ผ๋ฏ๋ก ์ข
๋ฃ
}
for(int i = 0; i < 5; i++){
cnt++; // ๋ฌธ์์ด์ ์์ฑํ ๋๋ง๋ค ์ธ๋ฑ์ค ์ฆ๊ฐ
dfs(cur+dict[i],word); // ํ์ฌ ๋ฌธ์์ด์ ๋ชจ์์ ์ถ๊ฐ ํ DFS ์ฌ๊ท ํธ์ถ
}
}
}
DFS๋ฅผ ํ์ฉํ์ฌ ๋ชจ๋ ๊ฐ๋ฅํ ๋ชจ์ ์กฐํฉ์ ์์ฑํ๋ฉฐ, ๊ฐ ์กฐํฉ์ด ์ฃผ์ด์ง ๋จ์ด์ ์ผ์นํ๋ ์ง ํ์ธํ๋ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์๋ค.
์ค์ค ์ ๋ ํ์ด๋ด์ผ๊ฒ ์ด์๐