[programmers] ๋ชจ์์ฌ์ - Java
์ํ๋ฒณ ๋ชจ์ 'A', 'E', 'I', 'O', 'U'๋ก ๋ง๋ค ์ ์๋ ๊ธธ์ด 5 ์ดํ์ ๋จ์ด๊ฐ ์ฌ์ ์ ์๋ก๋์ด ์์ ๋, ์ฃผ์ด์ง ๋จ์ด๊ฐ ์ฌ์ ์์ ๋ช ๋ฒ์งธ ๋จ์ด์ธ์ง ์ฐพ๋ ๋ฌธ์ ์
๋๋ค. DFS ๋ฐฉ์์ผ๋ก ์ฌ์ ์ ์์ฑํ๊ณ , ํด๋น ์ฌ์ ์์ ๋จ์ด๊ฐ ์ถํํ๋ ์์๋ฅผ ์ฐพ์ ๋ฆฌํดํ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ์ต๋๋ค. ์ด ๋ฐฉ๋ฒ์ ์ฌ์ ์ ์์ฑํ์ง ์๊ณ ๋ ๊ฐ์ ์ถ๋ ฅํ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ ์์ฑํ๋ ๋ฐ ๋์ ํ๋ ๊ณ๊ธฐ๊ฐ ๋์์ต๋๋ค.
Apr 18, 2024
๋ชจ์์ฌ์
๋ฌธ์ ์ค๋ช
์ฌ์ ์ ์ํ๋ฒณ ๋ชจ์ 'A', 'E', 'I', 'O', 'U'๋ง์ ์ฌ์ฉํ์ฌ ๋ง๋ค ์ ์๋, ๊ธธ์ด 5 ์ดํ์ ๋ชจ๋ ๋จ์ด๊ฐ ์๋ก๋์ด ์์ต๋๋ค. ์ฌ์ ์์ ์ฒซ ๋ฒ์งธ ๋จ์ด๋ "A"์ด๊ณ , ๊ทธ๋ค์์ "AA"์ด๋ฉฐ, ๋ง์ง๋ง ๋จ์ด๋ "UUUUU"์
๋๋ค.
๋จ์ด ํ๋ word๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ด ๋จ์ด๊ฐ ์ฌ์ ์์ ๋ช ๋ฒ์งธ ๋จ์ด์ธ์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- word์ ๊ธธ์ด๋ 1 ์ด์ 5 ์ดํ์ ๋๋ค.
- word๋ ์ํ๋ฒณ ๋๋ฌธ์ 'A', 'E', 'I', 'O', 'U'๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
word | result |
"AAAAE" | 6 |
"AAAE" | 10 |
"I" | 1563 |
"EIO" | 1189 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
์ฌ์ ์์ ์ฒซ ๋ฒ์งธ ๋จ์ด๋ "A"์ด๊ณ , ๊ทธ๋ค์์ "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... ์ ๊ฐ์ต๋๋ค. "AAAAE"๋ ์ฌ์ ์์ 6๋ฒ์งธ ๋จ์ด์
๋๋ค.
์
์ถ๋ ฅ ์ #2
"AAAE"๋ "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"์ ๋ค์์ธ 10๋ฒ์งธ ๋จ์ด์
๋๋ค.
์
์ถ๋ ฅ ์ #3
"I"๋ 1563๋ฒ์งธ ๋จ์ด์
๋๋ค.
์
์ถ๋ ฅ ์ #4
"EIO"๋ 1189๋ฒ์งธ ๋จ์ด์
๋๋ค.
solution.java
import java.util.*; class Solution { List<String> list; String[] arr = {"A", "E", "I", "O", "U"}; public int solution(String word) { int answer = 0; list = new ArrayList<>(); // ์ฌ์ ์์ฑ for(int i = 0 ; i < 5; ++i) makeWord(arr[i], 1); // ์ฌ์ ์์ ๋จ์ด ํ์ for(int i = 0; i < list.size(); i++){ if(list.get(i).equals(word)) return i + 1; } return answer; } // dfs๋ฅผ ์ด์ฉํ ์ฌ์ ์์ฑ public void makeWord(String base, int depth){ list.add(base); if(depth == 5){ return; } for(int i = 0 ; i < 5; ++i) makeWord(base + arr[i], depth + 1); } }
ํต์ฌ ํค์๋
- DFS ๋ฐฉ์์ผ๋ก ์ฌ์ ์ ์์ฑํ ํ, ํด๋น ์ฌ์ ์์ ๋จ์ด๊ฐ ์ถํํ๋ ์์๋ฅผ ์ฐพ์ ๋ฆฌํดํ๋ค.
- ์ฌ์ ์์ ํด๋น ๋จ์ด์ ์์๋ฅผ ์ฐพ๊ธฐ ์ํด์๋ ์์๋ฅผ ๋ณด์ฅํ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด์ผ ํ๋ฏ๋ก,
List
๋ฅผ ์ฌ์ฉํ๋ค.
๊ฒฐ๋ก !
์ฒ์ ํด๋น ๋ฌธ์ ์ ์ ๊ทผํ ๋ ์ฌ์ ์ ์์ฑํ์ง ์๊ณ ์
๋ ฅ ๊ฐ์ ์ด์ฉํด ๋ฐ๋ก ๊ฐ์ ์ถ๋ ฅํ๋ ค ํ์ง๋ง ์ฝ๋๊ฐ ์ ์์ฑ๋์ง ์์๋ค.
์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด 1๋ถํฐ 5๊น์ง์ ๊ธธ์ด๋ฅผ ๊ฐ์ง ๋ชจ๋ ๋จ์ด๋ฅผ ํฌํจํ๋ ์ฌ์ ์ ๋ฏธ๋ฆฌ ๋ง๋ค๊ณ , ํด๋น ์ฌ์ ์ ํ์ํ๋ ํํ๋ก ์ฝ๋๋ฅผ ์์ ํ๋ค.
์ถํ ์ฌ์ ์ ์์ฑํ์ง ์๊ณ ๋ ๊ฐ์ ์ถ๋ ฅํ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ ์์ฑํด๋ณด๊ณ ์ถ์๋ค.
Share article