[백준] 1759번: 암호 만들기 [C#]

주어진 알파벳들중 적어도 모음 1개, 자음 2개를 포함하는 n길이의 문자열을 사전 순으로 모두 구하는 문제이다.

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _1759_boj boj = new _1759_boj();
 
            boj.boj_1759();
 
        }
    }
        internal class _1759_boj
    {
        static StringBuilder sb = new StringBuilder();
        static int[] arr;
        static string[] input;
        static List<string> temp;
        static int ja = 0;
        static int mo = 0;
        public void boj_1759()
        {
            
            arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            input = Console.ReadLine().ToLower().Split();
            Array.Sort(input);
 
            temp = new List<string>();
 
            makeCombi(0, 0);
 
            if (sb[sb.Length - 1] == '\n')
            {
                sb.Remove(sb.Length - 1, 1);
            }
            Console.Write(sb);
        } // a c i s t w
        public void makeCombi(int depth, int breadth )
        {
            for (int j = depth + breadth ; j <= arr[1] - (arr[0] - depth); j++)
            {
                temp.Add(input[j]);
                if (temp[temp.Count() - 1] == "a" || temp[temp.Count() - 1] == "e" || temp[temp.Count() - 1] == "i" || temp[temp.Count() - 1] == "o" || temp[temp.Count() - 1] == "u")
                    mo++;
                else
                    ja++;
 
                if (temp.Count() == arr[0] && (mo >= 1 && ja >= 2))
                {
                    foreach (var _ in temp)
                        sb.Append(_);
                    sb.Append('\n');
                }
                if (temp.Count() < arr[0])
                    makeCombi(depth + 1, breadth);
 
                if (temp[temp.Count() - 1] == "a" || temp[temp.Count() - 1] == "e" || temp[temp.Count() - 1] == "i" || temp[temp.Count() - 1] == "o" || temp[temp.Count() - 1] == "u")
                    mo--;
                else
                    ja--;
                temp.RemoveAt(temp.Count() - 1);
               breadth++;
            }
        }
    }
}
 
 

 

처음 봤을 때엔 쉬운 문제라고 생각이 들었었다. 하지만 막상 문제를 풀어보니 생각보다 복잡한 문제였다.

일단 출력 조건이 문자열을 사전순으로 출력하는 것이었다. 어차피 문자열을 사전순으로 만들면 출력도 사전순으로 될 테니 입력받은 문자열을 정렬해주는 것으로 대신하였다.

 

문자열을 만드는 함수를 재귀함수로 만드는 것이 꽤나 힘들었다.

첫번째 문자는 a, c. i가 올 수 있고, 두번쨰 문자는 c, i, s가 올 수 있었는데, 시작점은 변동되지만 (첫번째 문자는 0, 1, 2번 인덱스, 두번째 문자는 1, 2, 3번째 인덱스) 종료점은 불변 (첫번째 문자는 2번 인덱스 까지, 두번째 문자는 3번 인덱스 까지) 한 특징을 구현하기 위해 깊이와 너비의 개념을 떠올렸다.

 

문자열이 완성될때 까지 깊이를 증가시켜준다. 문자열이 완성되면, 이후에는 너비를 증가시켜주며 종료점까지 문자열을 만들어준다.

 

모든 문자열이 만들어지면, 마지막줄에 있는 빈줄을 삭제시켜 주며 출력을 했다.