๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 16์ผ์ฐจ TIL - ๋ชจ์Œ ์‚ฌ์ „

HOONSSACยท2024๋…„ 8์›” 7์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
16/41
post-thumbnail

โณ๋ฌธ์ œ

๋ฌธ์ œ ์„ค๋ช…

์‚ฌ์ „์— ์•ŒํŒŒ๋ฒณ ๋ชจ์Œ 'A', 'E', 'I', 'O', 'U'๋งŒ์„ ์‚ฌ์šฉํ•˜์—ฌ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š”, ๊ธธ์ด 5 ์ดํ•˜์˜ ๋ชจ๋“  ๋‹จ์–ด๊ฐ€ ์ˆ˜๋ก๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์‚ฌ์ „์—์„œ ์ฒซ ๋ฒˆ์งธ ๋‹จ์–ด๋Š” "A"์ด๊ณ , ๊ทธ๋‹ค์Œ์€ "AA"์ด๋ฉฐ, ๋งˆ์ง€๋ง‰ ๋‹จ์–ด๋Š” "UUUUU"์ž…๋‹ˆ๋‹ค.

๋‹จ์–ด ํ•˜๋‚˜ word๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ด ๋‹จ์–ด๊ฐ€ ์‚ฌ์ „์—์„œ ๋ช‡ ๋ฒˆ์งธ ๋‹จ์–ด์ธ์ง€ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • word์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 5 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • word๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž 'A', 'E', 'I', 'O', 'U'๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

wordresult
"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๋ฒˆ์งธ ๋‹จ์–ด์ž…๋‹ˆ๋‹ค.


โœ๏ธํ’€์ด

์ด ๋ฌธ์ œ๋Š” "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๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ ๋ชจ์Œ ์กฐํ•ฉ์„ ์ƒ์„ฑํ•˜๋ฉฐ, ๊ฐ ์กฐํ•ฉ์ด ์ฃผ์–ด์ง„ ๋‹จ์–ด์™€ ์ผ์น˜ํ•˜๋Š” ์ง€ ํ™•์ธํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜์˜€๋‹ค.


๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 7์ผ

์˜ค์˜ค ์ €๋„ ํ’€์–ด๋ด์•ผ๊ฒ ์–ด์š”๐Ÿ˜Š

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ