[백준 - C#] 1251번 단어 나누기

문제링크

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

1251번: 단어 나누기

 

문제

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다.
각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고,
이를 다시 원래의 순서대로 합친다.

예를 들어,

• 단어 : arrested
• 세 단어로 나누기 : ar / rest / ed
• 각각 뒤집기 : ra / tser / de
• 합치기 : ratserde

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.

출력

첫째 줄에 구하고자 하는 단어를 출력하면 된다.

 

문제정리

1. 세 개의 더 작은 단어로 나눈다.
2. 단어 각각은 최소 길이가 1 이상인 단어이다.
3. 나눈 단어들을 앞뒤로 뒤집고 다시 합친다.
4. 사전순으로 가장 앞서는 단어를 출력 한다.

이번 문제의 경우 단어를 삼등분 하여 리버스 하고 다시 합친 단어들을 나열하여 사전에서 가장 앞서는 단어를 출력하는 문제입니다.

결국 모든 단어들을 찾은 다음 오름차순으로 정렬하여 나온 값 중 제일 첫번째 값을 가지고 오면 되는 문제입니다.

저 같은 경우 삼등분 구역을 정하기 위해 left 값과 right 값을 선정하여 앞에서부터 모든 단어들을 찾았습니다.

예제로 확인해보면 (left/right 단어1 단어2 단어3)
1/2 m o letib => 1/3 m bo leti => 1/4 m ibo let => 1/5 m tibo le => 1/6 m etibo l
2/3 om b leti => 2/4 om ib let => 2/5 om tib le => 2/6 om etib l
3/4 bom i let => 3/5 bom ti le => 3/6 bom eti l
4/5 ibom t le => 4/6 ibom et l => 5/6 tibom e l

주의 할점으로는 단어 각각의 최소 길이는 1이상이여야 한다는 겁니다! 

더 자세한 내용은 아래 코드를 보시면 확인해 볼 수 있습니다.

 

아래 코드에서 사용한 새로운 문법입니다.

• 인덱스 및 범위

C# 8.0의 새로운 기능 - C# 가이드

 

C# 코드

static void Main(string[] args)
{
    // 1251 단어 나누기
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string input = reader.ReadLine();
 
    int left = 1; // 삼등분 해야되는 왼쪽 값
    int right = 2; // 삼등분 해야하는 오른쪽 값
    int length = input.Length;
    List<string> result = new List<string>();
 
    while (true)
    {
        char[] a = input[..left].ToArray(); // 삼등분한 첫번째 단어
        Array.Reverse(a);
 
        char[] b = input[left..right].ToArray(); // 삼등분한 두번째 단어
        Array.Reverse(b);
 
        char[] c = input[right..length].ToArray(); // // 삼등분한 세번째 단어
        Array.Reverse(c);
 
        result.Add(new string(a) + new string(b) + new string(c));
 
        right++;
 
        if (right >= length) // right의 값이 총 길이를 넘기면 left값 증가시키고 right값을 left+1로 초기화
        {
            left++;
            right = left + 1;
 
            if (right >= length) // 초기화 후에도 length 보다 크다면 반복문 종료
                break;
        }
    }
 
    result.Sort(); // 사전상 가장 앞에 있는 단어 오름차순 정렬
 
    writer.WriteLine(result[0]);
 
    writer.Close();
    reader.Close();
}
 

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