[JAVA] 백준 1251_단어 나누기

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

📌 문제 탐색하기

입력한 단어에서 임의로 2개의 부분을 나눠서 3개의 덩어리로 만들어주고 -> 각각 3개의 단어를 뒤집고 -> 다시 뒤집은 단어들을 하나로 합친다.

이때 단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.
라는 조건에 맞추어 조합을 사용해야한다. ? 

📌 가능한 시간복잡도

일단, 문자열에서 두개의 자리르 ㄹ골라서 3개의 덩어리로 나눠야함. 이때 가능한 조합은 문자열의 길이 N일때, N^2이다.
따라서 조합의 수 O(N^2) + 각각 나누어진 조각들을 reverse()함수를 활용해서 뒤집고 붙이는 과정이므로 O(N) 

따라서, 가능한 시간복잡도는 O(N^2) + O(N)이다. 

📌 코드 설계하기

우선, 문자열을 무작위로 2군데를 나눠야하니까 문자열을 나눌 위치를 2중 for문을 사용해서 반복문으로 돌리고 ->
각각 나눠진 3개의 덩어리 단어를 각각 reverse() 함수를 활용해서 뒤집어준다. -> 뒤집어진 단어들을 합쳐서 출력한다. ( 이때, 사전순으로 가장 앞서는 단어를 출력해야하기때문에 모든 가능한 경우의 수를 조합해서 처리하고 가장 알맞은 결과값을 출력해야함 ) 

 

📌 정답 코드

import java.util.*;

public class S03 { //백준1251 문제
    public String solution(String str) {
        String answer = null;
        int len = str.length();
        List<String> candidates = new ArrayList<>();

        for (int i = 1; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                String part1 = new StringBuilder(str.substring(0, i)).reverse().toString();
                String part2 = new StringBuilder(str.substring(i, j)).reverse().toString();
                String part3 = new StringBuilder(str.substring(j)).reverse().toString();

                String combined = part1 + part2 + part3;
                candidates.add(combined);
            }
        }

        Collections.sort(candidates);
        answer = candidates.get(0);

        return answer;
    }

    public static void main(String[] args){
        S03 T = new S03();
        Scanner sc = new Scanner(System.in);
        String text = sc.next();
        System.out.println(T.solution(text));
    }
}