코딩테스트 준비 - 단어나누기

혼자서 다시푸는 코딩테스트 준비 일지 - 39

브루트포스수학배열정렬

2 months ago

5 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 1251.단어나누기
사용언어 : C#
난이도 : 중
풀이시간 : 43m
유형 : 브루트포스, 수학, 배열, 정렬

문제

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

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

예를 들어,

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

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

입력

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

출력

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

예제 입력 1 복사

mobitel

예제 출력 1 복사

bometil

문제 풀이 접근

이 문제의 핵심은 두가지인 것으로 보인다.
총 3개로 단어를 나누는 인덱스 접근을 오류없이 빠르게 작성하는 방법, 문자열의 정렬은 각각의 인덱스 앞의 값부터 사전순 정렬을 한다는 점 이다.

아무리 인덱스 접근을 빠르게 한다고 한들, 문자열의 정렬이 사전순으로 한다는 것을 모르면 해결하기 어려울 것이다.

나는 2중 for 문을 사용하였고 예를든 a r r e s t e d 을 i 는 a , j 는 r , 이하 나머지는 3번째 문자열로 취급하도록 했다.

i가 증가함에 따라 j도 증가하고, (i+j) < arr.Length 가 가장 중요한 두번째 반복문에서의 조건이었다.
하나씩 모두 구해서 리스트에 넣은다음, 오름차순으로 정렬을 수행하면 쉽게 구할 수 있는 문제였다.

작성 코드 (C#)

using System;
using System.Collections;
using System.Collections.Generic;
using static CodingTestProj.Program;

/*
 * Difficulty : Middle
 * URL : https://www.acmicpc.net/problem/1251
  * Time : 43m
 */


//mobitel
namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var ss = new Solution();
            ss.Solve();
        }
    }

    public class Solution
    {
        public string _in;
        public string _ret;

        List<string> _sorted_list = new List<string>();

        public void Solve()
        {
            _ret = string.Empty;
            _in = Console.ReadLine();

            for(int i = 1; i < _in.Length -1; ++i)
            {
                string copy = _in;
                string _1 = copy.Substring(0, i);

                for (int j= 1; (j+i) < _in.Length; ++j)
                {
                    string _2 = copy.Substring(i, j);
                    string _3 = copy.Substring(j+1+(i-1),copy.Length-(1+j+(i-1)));

                    char[] _1arr = _1.ToCharArray();
                    char[] _2arr = _2.ToCharArray();
                    char[] _3arr = _3.ToCharArray();

                    Array.Reverse(_1arr);
                    Array.Reverse(_2arr);
                    Array.Reverse(_3arr);

                    string __1 = new string(_1arr);
                    string __2 = new string(_2arr);
                    string __3 = new string(_3arr);

                    string _combine = __1 + __2 + __3;

                    _sorted_list.Add(_combine);
                }
            }

            _sorted_list.Sort();

            if (_sorted_list.Count > 0)
                _ret = _sorted_list[0];

            print();
        }

        public void print()
        {
            Console.WriteLine(_ret);
        }
    }
}