๐ ํ๋ก๊ทธ๋๋จธ์ค / ์์ ํ์ / Level2 / ๋ชจ์์ฌ์
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- word์ ๊ธธ์ด๋ 1 ์ด์ 5 ์ดํ์ ๋๋ค.
- word๋ ์ํ๋ฒณ ๋๋ฌธ์ 'A', 'E', 'I', 'O', 'U'๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
๐ ์ ์ถ๋ ฅ ์
| word | result |
| "AAAAE" | 6 |
| "AAAE" | 10 |
| "I" | 1563 |
| "EIO" | 1189 |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ๋จ์ด ์์ฑ ์์ ์ดํด
โก๏ธ ๋จผ์ ๋จ์ด์ ์์ฑ ์์์ ๋ํด์ [A, B, C] ์ ์งง์ ๋ฐฐ์ด๋ก ์ ๋ฆฌํด๋ณด์๋ค.

๊ทธ๋ฆผ์ ๊ทธ๋ ค๋ณด๋ ์ ๋ฒ ํผ๋ก๋ ๋ฌธ์ ์ ์ ์ฌํ๋ค๋ ๊ฒ์ ์ ์ ์์๋ค. ํผ๋ก๋ ๋ฌธ์ ์ ๊ฒฝ์ฐ ์ผ๋ฐ ์์ด(nPr)๋ก์ visited ๋ฐฐ์ด์ ํ์ฉํ์ฌ ์ค๋ณต์ ํผํ๋ค๋ฉด, ์ด๋ฒ ๋ฌธ์ ๋ ์ค๋ณต ์์ด(nΠr) ๋ก ๋ฐ๋๋ก visited ๋ฐฐ์ด์ ์ฌ์ฉํ์ง ์๊ณ ๋๋ฆฌ๋ฉด ์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ ์์๋ก ์ถ๋ ฅ์ด ๊ฐ๋ฅํ๋ค.
๋ฐ๋ผ์ ํต์ฌ์ฝ๋๋
// arr ๋ฐฐ์ด : ๊ธฐ์กด ์ฃผ์ด์ง ๋ฐฐ์ด
// output ๋ฐฐ์ด : ๊ฒฐ๊ณผ๊ฐ์ ๋ด๋ ๋ฐฐ์ด
public void dfs (...) {
if (depth == ์ต๋๊น์ด) {
return;
}
for (int i=0; i<๋ฐฐ์ด์ ๊ธธ์ด; i++ {
output[depth] = arr[i];
dfs(...); // ์ฌ๊ท ํธ์ถ
}
}
์ผ๋ก ๋ฐ๋๋ก ์ผ๋ฐ ์์ด๋ณด๋ค ํจ์ฌ ๊ฐํธํด์ง ๊ฒ์ ์ ์ ์๋ค.
2๏ธโฃ ์ฃผ์ด์ง ๋ฌธ์์ด๊ณผ ์ค๋ณต์์ด์ ๊ฒฐ๊ณผ๊ฐ์ด ์ผ์นํ๋์ง๋ฅผ ํ์ธํ๋ ๊ณผ์
โก๏ธ ์ฒ์์๋ ๋ฌธ์์ด๋ก ํด๊ฒฐ์ ํด๋ณด๋ ค๊ณ ํ๋๋ฐ, ๊ทธ๋ ๊ฒ๋๋ฉด depth ๊ฐ ๋ณํํจ์ ๋ฐ๋ผ ๋ฌธ์์ด์ substring ํ๋ ๊ณผ์ ์ด ๋จธ๋ฆฟ์์ ์ ๊ทธ๋ ค์ง์ง ์์์ ์ฃผ์ด์ง ๋ฌธ์์ด์ split ์ ํตํด ํ๊ธ์์ฉ ๋ฐฐ์ด์ ๋ด๊ณ , ์ค๋ณต์์ด์ ๋งค ๋จ๊ณ ๊ฒฐ๊ณผ๊ฐ์ธ ๋ฐฐ์ด output ๊ณผ Arrays ์ ๋ด์ฅํจ์์ธ equals๋ฅผ ํ์ฉํด์ ์ผ์น๋ฅผ ํ์ธํ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ค.

๐ป ํ์ด ์ฝ๋
import java.util.Arrays;
class Solution {
public static String[] alphabet = {"A", "E", "I", "O", "U"}; // ๋ชจ์
public static String[] words; // ์ชผ๊ฐ์ง ๋ฌธ์์ด์ ๋ด๊ธฐ์ํ ๋ฐฐ์ด
public static int answer = 0;
public static boolean go = true;
public int solution(String word) {
// ์ฃผ์ด์ง ๋ฌธ์์ด์ ๋ฐฐ์ด๋ก ์ชผ๊ฐ๋ ๊ณผ์
words = word.split("");
dfs (0, new String[words.length]);
return answer;
}
public static void dfs (String[] words, int depth, String[] output) {
if (depth == 5) {
return;
}
for (int i=0; i<5; i++) {
// ํ์ํ ๋ด์ฉ๋ง ๋ด๊ธฐ์ํด ์ฃผ์ด์ง ๋ฌธ์์ด ๊ธธ์ด์ ํด๋นํ๋ ๋งํผ๋ง ์ ์ฅ
if (depth < words.length) {
output[depth] = alphabet[i];
}
answer++;
// ์ฃผ์ด์ง ๋ฌธ์์ด๊ณผ ์ผ์นํ๋์ง ํ์ธ
if (depth == words.length-1 && Arrays.equals(words, output)) {
go = false; // ํด๋ต์ ์ฐพ์ผ๋ฉด ์ฌ๊ท๋ฅผ ๋ฉ์ถค
break;
}
// ์ฌ๊ท
dfs(depth+1, output);
if (!go) { // ํด๋ต์ ์ฐพ์ผ๋ฉด ์ฌ๊ท๋ฅผ ๋ฉ์ถค
return;
}
}
}
}
GitHub - Young998904/Practice_Algorithm_Auto: JAVA ์๊ณ ๋ฆฌ์ฆ ์ ์ฅ์ ๐ฅ (๋ฌธ์ ์ ํจ๊ป ์๋ ์ปค๋ฐ)
JAVA ์๊ณ ๋ฆฌ์ฆ ์ ์ฅ์ ๐ฅ (๋ฌธ์ ์ ํจ๊ป ์๋ ์ปค๋ฐ). Contribute to Young998904/Practice_Algorithm_Auto development by creating an account on GitHub.
github.com