[BAEKJOON] 백준 16719: ZOAC (C#)

문제 링크

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

 

 

문제

2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.

앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!

규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.

예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.

바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.

 

 

입력

첫 번째 줄에 알파벳 대문자로 구성된 문자열이 주어진다. 문자열의 길이는 최대 100자이다.

 

 

출력

규칙에 맞게 순서대로 문자열을 출력한다.

 

 

 

통과한 답안

namespace _16719
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string input = Console.ReadLine();
            bool[] visited = new bool[input.Length];

            for (int i = 0; i < input.Length; i++)
            {
                int j = input.Length - 1;
                while (j >= 0 && visited[j]) j--;

                int min = j;

                while (j >= 0 && !visited[j])
                {
                    min = input[min] >= input[j] ? j : min;
                    j--;
                }

                visited[min] = true;

                for (int k = 0; k < input.Length; k++)
                {
                    if (visited[k])
                    {
                        Console.Write(input[k]);
                    }
                }
                Console.WriteLine();
            }
        }
    }
}

주어진 문자열을 한 글자 추가했을 때의 문자열 중에서 사전 순으로 가장 앞에 나오는 문자를

한 글자씩 추가하며 보여주도록 코딩해야되는 문제이다.

 

문제의 조건이 조금 이해하기 난해할 수 있는데, 조금 더 자세히 설명하면,

ZOAC의 문자를 한 글자씩 추가해서 표현한다면,

한 글자에서 사전에서 가장 앞에 나오는 글자는 A이고

두 글자에서 사전에서 가장 앞에 나오는 글자는 AC이고

세 글자에서 사전에서 가장 앞에 나오는 글자는 OAC이고

네 글자는 원 글자가 나타나게 된다.

이 때, 글자를 추가하는 것이므로 주어진 문자열에서 각 문자의 위치는 고정이다.

 

따라서 STARTLINK의 경우에는

A

AI

AIK

AINK

ALINK

ARLINK

ARTLINK

SARTLINK

STARTLINK

가 되는 것이다.

 

즉, 이 문제를 해결하기 위해서 사전에서 가장 앞에 나오는 문자를 찾은 뒤에

STARTLINK의 경우 A

A를 출력하고, A 뒤에 있는 문자들에 대해서 다시 사전에서 가장 앞에 나오는 문자를 찾는다.

다음의 문자는 R, T, L, I, N, K 이므로 가장 앞에 나오는 문자는 I이다.

따라서 AI를 출력하고, I뒤에 있는 문자들에 대해서 다시 같은 과정을 반복한다.

다음의 문자는 N, K 이므로 가장 앞에 나오는 문자는 K이다.

따라서 AIK를 출력하고 K 뒤에는 문자가 없으므로, 다시 I로 돌아온다.

I뒤에는 N만 남아 있으므로 AINK를 출력한다.

이후에 I뒤에 문자가 없으므로 A로 돌아오면,

R, T, L이 남아 있으므로  ALINK를 출력하고, L뒤에는 문자가 없으므로 A로 돌아오면

R, T가 남아있으므로 ARLINK를 출력하고, R 뒤에 있는 문자인 T를 출력한다.

이를 통해서 ARTLINK를 출력했으며, A뒤에 남은 문자가 없으므로 앞으로 돌아가면,

S, T가 남아 있고 이 둘 중에서 사전에 앞에 나오는 문자는 S이므로,

SARTLINK를 출력하고 남아있는 T를 선택하여

최종적으로 STARTLINK를 출력하게된다.

 

따라서 이를 재귀를 이용해서 문제를 풀면,

주어진 문자열에서 가장 앞에 나오는 문자를 찾고, 출력한다.

그 문자를 기준으로 오른쪽에 있는 문자들 중에서 가장 앞에 나오는 문자를 찾고 출력한다.

이를 각 기준의 오른쪽에 문자가 남지 않을때까지 반복한 후에

기준보다 왼쪽에 문자가 있다면 해당하는 문자들을 가지고 다시 반복한다.

이러한 방식으로 문제를 해결할 수 있다.

 

 

아마도 이 문제의 출제의도는 위의 방법을 이용하여 풀이한 것으로 추측되는데

내가 문제를 풀이한 방법은 조금 다르게 풀이하였다.

 

우선 주어진 문자열과 같은 길이의 bool 배열을 선언한 뒤에

이 배열을 이용하여 해당 알파벳이 방문되었는지 기록한다.

이후에 문자열을 순회하면서 뒤에서부터 방문하지 않은 문자를 찾은 후에

해당 문자의 인덱스를 저장하고,

두 번째 while문을 통해서 방문하지 않은 문자들 중에서 가장 작은 문자를 찾는다.

최종적으로 visited배열의 min인덱스에 있는 문자를 방문했음을 기록한다.

 

이후에 for문을 이용하여 visited 배열에서 true인 문자들을 Write로 출력하고,

for문 이후에 줄바꿈을 사용하여 입력값들에서 true(방문한)인 문자들을 출력하도록 구현하였다.

 

이는 위의 재귀의 방법이 아닌, 입력된 문자들 중에서

방문하지 않은 가장 작은 값(A에 가까운)을 찾아서 bool로 표기하는 과정을 반복하며

각 반복에서 true로 표시된 문자들을 출력하도록 구현하여

새롭게 문자를 생성하며 인덱스를 고민할 필요 없이 해결할 수 있었다

(만약 문자열의 길이가 길어져 시간 초과가 발생한다면 StringBuilder를 이용해

 Append로 각 문자를 추가하고, Console.WriteLine()이 있는곳에서 출력하고

 Clear()하는 방식으로 해결할 수 있을 것이다).

 

 

조금은 난이도가 있었던 문제로,

초기에 고안했던 방법이 문자를 추가하는 인덱스를 찾는 과정에서 문제가 발생하여

새로운 방법으로 해결하려고 시도했던 문제였다.

이후에 초기에 고안했던 재귀를 통해서도 문제를 풀 수 있도록 시도해볼 예정이다.