[백준 알고리즘] 1251번 : 단어 나누기 (Java) 문제 풀이

2 초

128 MB

8010

3383

2882

46.342%

문제

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

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

예를 들어,

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

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

입력

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

출력

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

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

1251번: 단어 나누기

문제에 대한 이해

주어진 단어를 통해 임의로 3개의 문자로 나누어 뒤집고 붙이는 과정을 통해, 이렇게 만든 단어를 쭈욱 정렬 하였을 때 사전순을 가장 앞에 오는 단어를 출력하는 문제이다. 문제를 읽고, 문자열과 브루트포스 알고리즘을 생각하였다.

어떻게 풀 것인가?

위에 언급했던 것 처럼 브루트 포스 알고리즘을 생각하여 문제에서 주어진 

1. 세 단어로 나누기

2. 세 단어를 뒤집기

3. 세 단어를 하나의 단어로 만들기

라는 과정을 계속 반복하고 하나의 List에 담은 이후 Collection.sort()를 이용하여 정렬하고 맨 앞에 있는 요소를 출력하면 된다고 생각하였다.

시간복잡도

시간 복잡도는 O(N^2) 이다.

공간복잡도

시간 복잡도는 list에 대한 점에서 O(N)이다.

풀면서 놓쳤던점

크게 없이 한번에 통과하였다.

이 문제를 통해 얻어갈 것

문자열과 브루트포스에 대해서 공부할 수 있었다.

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        LinkedList<String> list = new LinkedList<>();
        for (int i = 2; i < str.length(); i++) {
            for (int j = 1; j < i; j++) {
                StringBuilder strSb1 = new StringBuilder(str.substring(0, j));
                StringBuilder strSb2 = new StringBuilder(str.substring(j, i));
                StringBuilder strSb3 = new StringBuilder(str.substring(i));
                String str1 = strSb1.reverse().toString();
                String str2 = strSb2.reverse().toString();
                String str3 = strSb3.reverse().toString();
                list.add(str1 + str2 + str3);

            }
        }
        Collections.sort(list);
        System.out.println(list.pop());

    }

}