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

오늘의 TIL은 프로그래머스의 옹알이 문제이다.

 

이 문제를 풀게된 이유는 프로그래머스의 AI 리포트라는 부분에서 추천 문제로 나온 것으로

 

AI 리포트에서 내가 여태까지 풀었던 문제들에 기반하여 나의 문제풀이 능력을 평가해주는데,

 

이 AI에서 나의 능력을 높이기 위해서 풀기 위한 문제로 추천해주었기에 풀게되었다.

 

예상 정답률이 69.1%인데 이 부분에서 불이 붙어서 풀게 되었다.

 

 

문제 링크

 

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

프로그래머스

 

문제에 대한 기본적인 내용은 아래와 같다.

 

string[] babbling으로 주어지는 배열에서

 

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

 

 

예를 들어서

 

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

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

 

다른 예로는

string[] babbling = { "ayaye", "uuuma", "ye", "yemawoo", "ayaa" }; 로 주어진다면

"aya" + "ye"로 "ayaye"는 가능하고, "ye"도 가능하고

"ye" + "ma" + "woo"도 가능하므로 정답은 3이다.

 

 

전체 코드는 아래와 같다.

 

namespace babbling01
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] str = { "aya", "ye", "woo", "ma" };
            string[] babbling = { "aya", "yee", "u", "maa", "wyeoo" };
            int answer = 0;

            foreach (string babble in babbling)
            {
                if (CanBabble(babble, str))
                {
                    answer++;
                }
            }

            Console.WriteLine(answer);
        }

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

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

            return false;
        }
    }
}

 

 

우선 static bool CanBabble 부분을 살펴보면 아래와 같은데

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

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

    return false;
}

 

if 문에서 babble의 길이가 0이라면 true를 반환하므로, answer의 카운트를 늘릴 수 있게 해준다.

 

그 아래 foreach 문에서 babbling의 원소들(여기서는 babble로 표기)이 주어진 4개의 단어로 시작하는 경우에

if 문 안의 if 문에서 해당 단어를 삭제한 후에 Cababble이 되는지 다시 확인한다.

 

이 부분이 이 코드의 핵심부분으로 재귀적으로 if문을 돌게 만들어서 모든 문자를 제거했다면 true를 return하게 하였다.

만약 그렇지 않다면 false를 return하게 하였다.

 

static void Main(string[] args)
{
    string[] str = { "aya", "ye", "woo", "ma" };
    string[] babbling = { "aya", "yee", "u", "maa", "wyeoo" };
    int answer = 0;

    foreach (string babble in babbling)
    {
        if (CanBabble(babble, str))
        {
            answer++;
        }
    }

    Console.WriteLine(answer);
}

 

이후에는 babbling으로 주어진 string[]의 각 원소에 대해 CanBabble을 확인하고

가능하다면 answer를 ++해서 카운트하도록 하였다.