문제

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

Silver V

코드 (Java)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        StringBuilder answer_builder = new StringBuilder();

        for (int i = 0; i < str.length(); ++i) {
            answer_builder.append('z');
        }
        String answer = answer_builder.toString();

        for (int i = 1; i <= str.length()-2; ++i) {
            for (int j = i + 1; j <= str.length() - 1; ++j) {
                String str1 = str.substring(0, i);
                String str2 = str.substring(i, j);
                String str3 = str.substring(j);
                String[] str_arr = {str1, str2, str3};
                StringBuilder rev_str = new StringBuilder();
                StringBuffer sb = new StringBuffer();
                for (String str_elem : str_arr) {
                    rev_str.append(str_elem);
                    rev_str.reverse();
                    sb.append(rev_str);
                    rev_str.setLength(0);
                }
                if (sb.toString().compareTo(answer) < 0) {
                    answer = sb.toString();
                }
            }
        }
        System.out.println(answer);
    }
}

풀이

처음엔 뭔가 간지나게 풀어야 하나 생각을 했었다. 그래서 이것저것을 시도했었다.

그러나 다 반례를 찾을 수 있었고, 조건 문자열 길이가 그렇게 길지 않고 나누는 가짓수가 많지 않다는 것을 파악

브루트포스 형식으로 풀기로 결정을 해서 위와 같이 했다.

자주 하는 생각이지만, 너무 간지나게 풀려고 할 필요는 없을 것 같다. 대신 좀 빠르게 구현을 하자.