백준 1251번 단어 나누기 (JAVA)

1251번 단어 나누기

문제

난이도

• 실버 5

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘
• 정렬

풀이

조합을 통해 나눌 구역을 선택한다.

3구역으로 나눌 때 각 구역은 최소 한 글자를 포함해야하기 0 ~ len - 1 까지의 수 중 2개의 수를 선택한다.

선택된 수로 나뉜 구역에 문자열을 뒤집고 새로운 문자열을 생성

문자열을 리스트에 담고 리스트를 정렬, 가장 첫 번째 문자열을 출력한다.

코드

public class Main {

    private static int len;
    private static char[] word;
    private static int[] number;
    private static List<String> list;

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        word = in.readLine().toCharArray();
        len = word.length;

        number = new int[2];
        list = new ArrayList<String>();


        comb(0, 0);

        Collections.sort(list);


        sb.append(list.get(0));
        out.write(sb.toString());
        out.close();
    }

    private static void comb(int start, int cnt) {

        if(cnt == 2) {
            String temp = "";
            int first = number[0]; // 0 ~ first
            int second= number[1]; // first + 1 ~ second
            int third = len; // second + 1 ~ len - 1

            for(int i = first; i >= 0; i--) {
                temp += word[i];
            }
            for(int i = second; i > first; i--) {
                temp += word[i];
            }
            for(int i = third - 1; i > second; i--) {
                temp += word[i];
            }

            list.add(temp);

            return;
        }

        for (int i = start; i < len -1; i++) {
            number[cnt]= i; 
            comb(i + 1, cnt + 1);

        }
    }
}