[BAEKJOON] 백준 27466: 그래서 대회 이름 뭐로 하죠 (C#)

문제 링크

https://www.acmicpc.net/problem/27466

 

 

문제

오늘도 운영진은 대회 이름을 정하고 있다. 몇 주째 대회 이름을 못 정하고 구글 드라이브, 지문/에디토리얼 파일, 디스코드 서버에 대회 이름으로 "대회 이름 뭐로 하죠"를 사용하고 있다.

그러던 어느 날, 그들은 KSA Automata Contest라는 이름을 떠올리게 되었고 대문자를 가져와서 KSAAC이라고 부르기로 했다. 이후 KSAAC의 발음이 "크사아악"인 사실을 알아채고 이름을 확정짓게 되었다.

운영진은 다음에 대회를 열 때는 원활한 진행을 위해 아래와 같이 대회 이름을 정하기로 했다.

• 먼저 협상을 통해 알파벳 대문자로 구성된 길이 N의 문자열 S를 정한다.
•  S에서 0개 이상의 문자를 지워서 대회 이름 T를 만든다.
• 이때 T는 길이가 M인 운영진이 좋아하는 이름이어야 한다. 운영진이 좋아하는 이름이란, 맨 뒷글자는 알파벳 자음(A부터 Z 중 A, E, I, O, U를 제외한 글자들)이고, 뒤에서부터 각각 두 번째와 세 번째 글자는 A인 문자열이다.

운영진이 또 다시 대회 이름을 정하기 위해 몇 주의 시간을 낭비하지 않도록 도와주자!

 

 

입력

첫 번째 줄에 두 정수 N, M이 주어진다.

두 번째 줄에는 문자열 S가 주어진다.

 

 

출력

첫 번째 줄에 위에서 설명한 방법으로 대회 이름을 정할 수 있으면 YES, 없으면 NO를 출력한다.

만약 정할 수 있으면 두 번째 줄에 대회 이름으로 가능한 문자열 T를 출력한다.

정답이 여러 개 존재한다면 아무거나 출력해도 상관없다.

 

 

제한

•  4≤M≤N≤3×10^5
•  S는 N개의 알파벳 대문자로 구성된 문자열

 

 

 

통과한 답안

using System.Text;

namespace _27466
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]);
            int M = int.Parse(inputs[1]);
            string S = Console.ReadLine();

            HashSet<char> consonants = new HashSet<char>("BCDFGHJKLMNPQRSTVWXYZ");

            StringBuilder sb = new StringBuilder();

            for (int i = N - 1; i >= 0; i--)
            {
                if (sb.Length == 0 && (consonants.Contains(S[i])))
                {
                    sb.Append(S[i]);
                }
                else if ((sb.Length == 1 || sb.Length == 2) && S[i] == 'A')
                {
                    sb.Append(S[i]);
                }
                else if (sb.Length > 2)
                {
                    sb.Append(S[i]);
                }

                if (sb.Length == M)
                {
                    break;
                }
            }

            if (sb.Length != M)
            {
                Console.WriteLine("NO");
            }
            else
            {
                Console.WriteLine("YES");
                string answer = sb.ToString();
                char[] charArr = answer.ToCharArray();
                Array.Reverse(charArr);
                answer = new string(charArr);
                Console.WriteLine(answer);
            }
        }
    }
}

 

길이가 N인 주어진 문자열에서 몇 개의 문자를 지워서 길이가 M인 문자열을 만드는 문제이다.

단, 길이가 M인 문자열의 마지막 문자는 자음이며,

마지막에서 두번째, 세번째 문자는 'A'인 새로운 문자열을 만들어야한다.

 

이 문제를 해결하기 위해서 StringBuilder(이하 sb)를 이용하였으며,

for문을 이용해서 S의 마지막 문자부터 첫 문자까지 순회하며

sb의 길이가 0인 경우에 현재 문자가 자음이면 sb에 추가,

sb의 길이가 1이나 2인 경우에 현재 문자가 A이면 sb에 추가,

sb의 길이가 2보다 큰 경우에는 현재 문자를 sb에 추가

sb의 길이가 M에 도달하면 for문을 조기 종료.

 

for문을 전부 순회한 후에 sb의 길이가 M이 아니라면 조건을 만족하지 못하므로 NO를 출력.

M이라면 YES를 출력하고 sb에 존재하는 문자열을 reverse하여 출력한다.

(이 때 sb에 Append를 이용하여 추가했으므로 sb에 있는 문자열은 reverse된 상태이다.

 이를 해결하기 위해서 Append 대신 Insert를 이용하여 sb를 구성하면

 N과 M의 값이 커짐에 따라서 시간 초과가 발생한다)