백준 1251 단어나누기[Java]

주어진 단어 를 3조각으로 나눠주고 그 조각의 역순을 이어 붙여 사전 순서로 했을때 제일 첫번쨰 단어를 반환하라는 문제의 조건이다. 

제일 처음 접근했던 나의 방법은 두개의 인덱스를 두어 가장 작은 알파벳을 찾아가면서 업데이틀 해가며 단어를 나눈다면 제일 작은 단어를 찾을수 있다고 생각을했다. 

즉 "mobitel" => b가 제일 작다 "mob" 나눠주고 , b다음 부터 시작점으로 다음 작은 알파벳을찾고 또 업데이트해주고 하면 예제의 있는답이 나온다. ㅋㅋㅋㅋ 틀렸다. 

통과못한 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        bf.close();

        StringBuilder sb = new StringBuilder();
        char[] arr = s.toCharArray();

        int start = 0;
        int end = 0;

        while (sb.length() != s.length()) {
            int minIdx = 0;
            char minChar = 'z' + 1;
            for (int i = start; i < arr.length; i++) {
                if (arr[i] < minChar) {
                    minChar = arr[i];
                    minIdx = i;
                }
            }
            end = minIdx;
            for (int i = end; i >= start; i--) {
                sb.append(arr[i]);
            }
            start = minIdx + 1;
        }
        System.out.println(sb.toString());
    }
}

"caba" 이런경우 acab 를 반환한다. abac 가 되어야 하는데... 그래서 생각한 두번째 방법이 나눠준 것들을 list 에 집어넣고 소팅후 이어붙혀주기로 했는데 ... 이것도 실패했다... ㅠㅠ
최후 의 보루 이중 for 문 으로 선택

패스코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        bf.close();

        List<String> result = new ArrayList<>();

        String[] willAdd = new String[3];
        for (int i = 1; i < s.length() - 1; i++) {
            for (int j = i + 1; j < s.length(); j++) {
                willAdd[0] = s.substring(0, i);
                willAdd[1] = s.substring(i, j);
                willAdd[2] = s.substring(j, s.length());

                String rs = "";
                for (String x : willAdd) {
                    StringBuilder sb = new StringBuilder(x);
                    rs += sb.reverse().toString();
                }
                result.add(rs);
            }
        }

        Collections.sort(result);
        System.out.println(result.get(0));
    }
}

패스했다.... 아니 이게 왜 되는거지,,, 곰곰히 생각을 해보니 알파벳 최대 50 개 2중 포문 돌아도 2500 번 나머지 몇개 연산한다고 하더라도 2초 안에 완전 넉넉하게 해결이 되더라 ... 이중포문 은 나에게 안좋은 인식이 있는데 이중포문이 나쁜게 아니라 문제범위 를 생각 못하고 코드갈긴 내가 나쁜놈 이였다...