단어 나누기

문제

알파벳 소문자로 이루어진 단어가 주어집니다. 이 단어를 임의의 두 부분을 골라서 세 개의 단어로 나눕니다. (나뉜 각 단어는 적어도 길이가 1 이상이어야 합니다.) 그 다음, 나뉜 세 개의 단어를 각각 순서를 뒤집은 후 다시 원래 순서대로 합칩니다. 이렇게 만들 수 있는 모든 단어들 중 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 영어 소문자로 된 단어가 주어집니다. 길이는 3 이상 50 이하입니다.
• 출력: 첫째 줄에 사전순으로 가장 앞서는 단어를 출력합니다.

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

풀이: 3분할 완전 탐색과 리스트 정렬

단어의 길이가 최대 50으로 매우 작기 때문에, 세 부분으로 나눌 수 있는 모든 경우의 수를 직접 구해보는 완전 탐색(Brute Force) 방식이 가장 적합합니다.

• 분할점 설정: 단어를 세 부분으로 나누기 위해 두 개의 자르는 위치 i와 j를 설정합니다.
  • i는 두 번째 단어의 시작 인덱스로, 1부터 문자열 길이 - 2까지 가능합니다.
  • j는 세 번째 단어의 시작 인덱스로, i + 1부터 문자열 길이 - 1까지 가능합니다.
• 문자열 뒤집기 및 병합: i와 j가 정해지면, 인덱스를 역순으로 순회하는 반복문 3개를 사용하여 각 단어를 뒤집고 StringBuilder에 추가합니다.
  1. 첫 번째 단어: 0부터 i - 1까지 역순 탐색
  2. 두 번째 단어: i부터 j - 1까지 역순 탐색
  3. 세 번째 단어: j부터 끝까지 역순 탐색
• 정렬 및 출력: 만들어진 새로운 단어들을 ArrayList에 모두 담고, Collections.sort()를 통해 사전순(오름차순)으로 정렬합니다. 가장 앞에 있는 요소(list.get(0))가 사전순으로 가장 앞서는 단어입니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       String s = br.readLine();

       List<String> list = new ArrayList<>();
       
       // i: 두 번째 단어의 시작점, j: 세 번째 단어의 시작점
       for (int i = 1; i < s.length() - 1; i++) {
          for (int j = i + 1; j < s.length(); j++) {
             StringBuilder sb = new StringBuilder();
             
             // 첫 번째 단어 뒤집어서 추가 (0 ~ i-1)
             for (int k = i - 1; k >= 0; k--) {
                sb.append(s.charAt(k));
             }

             // 두 번째 단어 뒤집어서 추가 (i ~ j-1)
             for (int k = j - 1; k >= i; k--) {
                sb.append(s.charAt(k));
             }

             // 세 번째 단어 뒤집어서 추가 (j ~ 끝)
             for (int k = s.length() - 1; k >= j; k--) {
                sb.append(s.charAt(k));
             }

             list.add(sb.toString());
          }
       }

       // 사전순 정렬
       Collections.sort(list);

       // 가장 앞서는 단어 출력
       bw.write(list.get(0));

       bw.flush();
    }
}

알고리즘 분류

문자열 (String), 브루트포스 알고리즘 (Brute Force), 정렬 (Sorting)