[programmers] ๋ชจ์Œ์‚ฌ์ „ - Java

์•ŒํŒŒ๋ฒณ ๋ชจ์Œ 'A', 'E', 'I', 'O', 'U'๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด 5 ์ดํ•˜์˜ ๋‹จ์–ด๊ฐ€ ์‚ฌ์ „์— ์ˆ˜๋ก๋˜์–ด ์žˆ์„ ๋•Œ, ์ฃผ์–ด์ง„ ๋‹จ์–ด๊ฐ€ ์‚ฌ์ „์—์„œ ๋ช‡ ๋ฒˆ์งธ ๋‹จ์–ด์ธ์ง€ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. DFS ๋ฐฉ์‹์œผ๋กœ ์‚ฌ์ „์„ ์ƒ์„ฑํ•˜๊ณ , ํ•ด๋‹น ์‚ฌ์ „์—์„œ ๋‹จ์–ด๊ฐ€ ์ถœํ˜„ํ•˜๋Š” ์ˆœ์„œ๋ฅผ ์ฐพ์•„ ๋ฆฌํ„ดํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ์‚ฌ์ „์„ ์ƒ์„ฑํ•˜์ง€ ์•Š๊ณ ๋„ ๊ฐ’์„ ์ถœ๋ ฅํ•  ์ˆ˜ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ž‘์„ฑํ•˜๋Š” ๋ฐ ๋„์ „ํ•˜๋Š” ๊ณ„๊ธฐ๊ฐ€ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.
DriedPollack's avatar
Apr 18, 2024
[programmers] ๋ชจ์Œ์‚ฌ์ „ - Java

๋ชจ์Œ์‚ฌ์ „

๋ฌธ์ œ ์„ค๋ช…

์‚ฌ์ „์— ์•ŒํŒŒ๋ฒณ ๋ชจ์Œ '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

More articles

See more posts

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ปDriedPollack's Blog