[BaekJoon] 1251 단어 나누기

1.  문제 링크

2.  문제

요약

• 알파벳 소문자로 이루어진 단어를 임의의 두 부분을 이용하여 세 개의 작은 단어로 나누고, 작은 단어들을 뒤집어 원래 순서대로 합쳤을 때, 사전순으로 가장 앞에 있는 단어를 찾습니다.
• 입력: 소문자로 된 단어 하나가 주어집니다.
• 출력: 뒤집어 원래 순서로 합쳤을 때, 사전순으로 가장 앞에 있는 단어를 출력합니다.

3.  소스코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public String reverseWord(String[] divWord) {
        String reverseWords = "";
        for(int i = 0; i < 3; i++) {
            for(int j = divWord[i].length(); j > 0; j--) {
                reverseWords += divWord[i].substring(j - 1, j);
            }
        }
        return reverseWords;
    }
    
    public String divideWord(String input) {
        if(input.length() == 3) {
            return input;
        }
        ArrayList<String> divWords = new ArrayList<String>();
        String[] divWord = new String[3];
        
        for(int i = 1; i < input.length() - 1; i++) {
            for(int j = i + 1; j < input.length(); j++) {
                divWord[0] = input.substring(0, i);
                divWord[1] = input.substring(i, j);
                divWord[2] = input.substring(j, input.length());
                
                divWords.add(reverseWord(divWord));
            }
        }
        
        Collections.sort(divWords);
        return divWords.get(0);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        Main m = new Main();
        System.out.println(m.divideWord(input));
    }
}

4.  접근

• brute force 방식을 이용하여 임의의 두 지점에서의 뒤집어진 단어를 구해서 가장 사전순으로 앞에 있는 단어를 반환합니다.
• 임의의 두 지점을 구할 때, 작은 단어의 길이는 1부터 가능하므로 첫 for문은 1부터 시작하고, 총 3개의 작은 단어가 필요하기 때문에 입력된 단어의 길이 - 2까지 for문을 진행합니다.
• 두 번째 for문은 첫 번째 for문 다음 글자부터 끝까지 진행합니다.
• 이렇게 찾은 두 지점은 substring에서의 끝나는 지점 부분에 사용할 것이기 때문에 두 번째 for문은 끝까지 진행해도 됩니다.
• 이렇게 세 개의 작은 단어로 나눈 후에, reverseWord 함수를 이용하여 세 작은 단어를 뒤집은 후, 원래 순서대로 합쳐 뒤집어진 단어를 만든 후에 반환합니다.
• 이렇게 모든 단어를 구했으면, 모든 단어를 사전순으로 정렬하여 가장 앞에 있는 것을 반환한 후, 이를 출력합니다.