[백준][BOJ 1251] - 단어 나누기

문제

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

1251번: 단어 나누기

 

 

문제 접근

• 입력으로 주어진 단어에 대해 문자열을 나누어 뒤집고, 이를 다시 조합하는 것이 가장 핵심적인 로직이다.
• 이때 만들 수 있는 모든 단어를 만들어야 하므로 어떻게 문자열을 나눌 것인지를 생각해야 한다.
  • 모든 경우의 수를 따져보아야 하므로 문제에서 제시된 조건인 각각의 문자열은 적어도 길이 1 이상이어야 한다를 만족하도록 문자열을 나누어 주면 된다.
  • 2중 for문으로 만들어낼 수 있다.
• 또한 사전 순으로 가장 앞서는 단어를 출력해야 하는데 이는 모든 데이터를 저장한 후에 정렬을 수행하여 가장 앞에 존재하는 문자열을 가져오도록 함으로서 구현할 수 있다.
• 다른 방법으로는 최소 힙을 사용하여 데이터가 저장될 때 마다 내부적으로 정렬이 자동으로 수행되도록 할 수 있다. 필자는 해당 방법을 사용하였다.

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String data = br.readLine();
    String[] divided = new String[3];
    PriorityQueue<String> pq = new PriorityQueue<>();

    for (int i = 1; i <= data.length() - 2; i++){
      divided[0] = data.substring(0, i);

      for (int j = i + 1; j <= data.length() - 1; j++){
        divided[1] = data.substring(i, j);
        divided[2] = data.substring(j);

        StringBuilder result = new StringBuilder();

        for (int k = 0; k < divided.length; k++){
          StringBuffer sb = new StringBuffer(divided[k]);
          result.append(sb.reverse().toString());
        }

        pq.offer(result.toString());
      }
    }

    System.out.println(pq.poll());
  }
}