[백준 - C#] 13417번 카드 문자열

문제링크

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

13417번: 카드 문자열

 

문제

N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다.
태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다.
가장 처음에 가져온 카드는 자신의 앞에 놓는다.
그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다.
태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자.
태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다.
다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다.

만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다.
이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.

N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

조건

시간제한 : 1초
메모리 제한 : 256 MB

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다. 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다. 

출력

출력은 표준 출력을 사용한다.
입력받은 데이터에 대해, 한 줄에 1개씩 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력한다.

 

문제정리

1. 가지고온 알파벳을 현재 입력된 문자열에 왼쪽 오른쪽에 붙여야 합니다.
2. 모든 경우의 수에서 사전 순으로 가장 빠른 문자열을 구해야합니다.
3. 모두 대문자입니다.

이번 문제의 경우 입력 받은 알파벳들을 왼쪽이나 오른쪽으로 이어 붙여 나열하여 나온 모든 문자열들 중에 가장 빠른 문자열을 구하는 문제입니다.

저는 맨 처음 기준이 되는 알파벳을 result List에 넣어주고 항상 0번째 값과 비교하여 작거나 같을 경우에 왼쪽에 붙여주고 아니면 오른쪽에 붙여 주어 사전순으로 가장 빠른 알파벳을 만들어 주었습니다.

 

주의 할점으로는 작거나 같다 즉 같은 값들도 포함시켜주어야 합니다.

 

C# 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

static void Main(string[] args) {     StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());     StreamReader reader = new StreamReader(Console.OpenStandardInput());       int T = int.Parse(reader.ReadLine());     List<char> result = new List<char>();       for (int i = 0; i < T; i++)     {         int N = int.Parse(reader.ReadLine());         char[] input = Array.ConvertAll(reader.ReadLine().Split(), char.Parse);           // 첫번째 알파벳 입력         result.Add(input[0]);           for (int j = 1; j < N; j++)         {             // 0번째 알파벳보다 작거나 같으면 왼쪽에 입력             if (result[0] >= input[j])                 result.Insert(0, input[j]);             else // 0번째 알파벳보다 크면 오른쪽에 입력                 result.Add(input[j]);         }           foreach (var o in result)             writer.Write(o);           writer.WriteLine();         result.Clear();     }       writer.Close();     reader.Close(); } Colored by Color Scripter

cs

 

 

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.