20240125_옹알이2(프로그래머스)

오늘의 TIL은 어제의 옹알이와 연결된 문제인 옹알이2이다.

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/133499

프로그래머스

 

옹알이2의 옹알이1과의 차이점은 네가지 발음을 여러번 사용할 수 있지만,

 

같은 발음을 연속해서는 사용할 수 없다는 점이 추가되었다.

 

문제를 정리하면 string[] babbling으로 주어지는 배열에서

 

"aya", "ye", "woo", "ma"를 최대 한 번씩 사용한 조합의 문자들이 몇개 있는지를 찾는 문제이다.

 

 

예를 들어서

 

string[] babbling = {"aya", "yee", "u", "maa", "wyeoo"}; 로 주어진다면

"aya"을 제외한 나머지는 주어진 문자들의 조합이 아니기 때문에 정답은 1이다.

 

다른 예로는

string[] babbling = { "ayaye", "uuu", "yeye", "yemawoo", "ayaayaa" }; 로 주어진다면

"aya" + "ye"로 "ayaye"는 가능하고, "ye" + "ma" + "woo" = "yemawoo"도 가능하므로 정답은 2이다.

("yeye"의 경우 "ye"가 연속되므로 발음이 불가능하다)

 

전체 코드는 아래와 같다.

 

using System;

public class Solution {
    public int solution(string[] babbling) {
        int answer = 0;
        
        string[] str = { "aya", "ye", "woo", "ma" };
        foreach (string babble in babbling)
        {
            if (CanBabble(babble, str))
            {
                answer++;
            }
        }
        
        return answer;
    }
    
    static bool CanBabble(string babble, string[] str)
    {
        if (babble.Length == 0)
        {
            return true;
        }

        foreach (var s in str)
        {
            if (babble.StartsWith(s))
            {
                if (CanBabbleNotSame(babble.Substring(s.Length), str, s))
                {
                    return true;
                }
            }
        }

        return false;
    }

    static bool CanBabbleNotSame(string babble, string[] str, string s)
    {
        if (babble.Length == 0)
        {
            return true;
        }

        foreach (var b in str)
        {
            if (babble.StartsWith(b) && b != s)
            {
                if (CanBabbleNotSame(babble.Substring(b.Length), str, b))
                {
                    return true;
                }
            }
        }

        return false;
    }
}

 

전반적인 내용은 어제의 옹알이1관 같은 풀이인데,

 

추가된 내용은 같은 단어가 연속으로 나오는 경우는 발음할 수 없으므로, 이를 판단하고 제외해야한다.

 

따라서 CanBabbleNotSame라는 bool 값을 새로 선언했는데, 내용은 아래와 같다.

 

static bool CanBabbleNotSame(string babble, string[] str, string s)
    {
        if (babble.Length == 0)
        {
            return true;
        }

        foreach (var b in str)
        {
            if (babble.StartsWith(b) && b != s)
            {
                if (CanBabbleNotSame(babble.Substring(b.Length), str, b))
                {
                    return true;
                }
            }
        }

        return false;
    }

 

원래 사용했던 CanBabble의 재귀함수를 사용하는 부분에서 if 문에 추가로 제약을 걸어준 것인데,

 

첫 번째 발음은 4개 중에 아무거나 들어와도 문제 없지만, 두 번째 발음부터는 첫 번째와는 다른 단어가 와야되므로,

 

이 bool 값에는 추가로 첫 번째 발음을 변수로 받아와서 if 문에서 사용하도록 하였다.

 

그 후에 재귀함수로 자기 자신을 반복하게 만들어 모든 단어들을 제거하면서 남는 string이 있는지 확인한다.

 

 

이 문제는 어제 문제를 푼 방법에서 사용한 방법들을 develop하여 문제를 풀이하였는데,

 

기존에 주어진 함수 등을 개선하여 추가로 주어진 조건에 맞는 문제를 푸는 경험이 되었다고 생각한다.

 

이 문제를 풀면서 생각한 것이 stringbuilder를 사용해서도 풀 수 있을 것으로 생각했는데,

 

추후에 이를 이용하여서도 문제를 풀이해보려고한다.