[자바] 백준 1251 - 단어 나누기 (java)

목차

문제 : boj1251

 

 

필요 알고리즘

• 브루트 포스
  
  • 3개의 단어로 나눌 수 있는 모든 경우를 확인해서 풀 수 있다.
• 정렬
  • 사전순으로 가장 앞서는 단어를 알기 위해 문자열에 대해 사전순으로 정렬을 해줘야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  단어의 최대 길이는 50이다. 따라서 3개의 단어로 나눌 수 있는 경우의 수는 대략 50x50가지 경우가 존재한다. 따라서 O(N^2)으로, 모든 경우를 다 봐도 풀 수 있는 문제이다.

 

  크게 로직은 다음과 같이 생각해볼 수 있다.

• 입력받은 문자열 s를 3개의 단어로 나눈다. 이 때 나누기 위한 두 지점의 인덱스를 a와 b라고 하겠다.

for (int a = 1; a < len; a++) {
    for (int b = a+1; b < len; b++) {
        // a와 b가 정해짐. 총 N*N 가지 경우의 수가 존재함.
    }
}

 

• s를 [0, a), [a, b), [b, 문자열 끝) 으로 세 조각으로 나눈다. 

StringBuilder s1 = new StringBuilder(s.substring(0, a));
StringBuilder s2 = new StringBuilder(s.substring(a, b));
StringBuilder s3 = new StringBuilder(s.substring(b));

 

• 세 조각의 앞뒤를 뒤집어 원래 순서대로 합친다.

sb.append(s1.reverse()).append(s2.reverse()).append(s3.reverse());

 

• 이렇게 합쳐진 문자열들을 정렬해서 사전순으로 가장 앞서는 단어를 출력한다.

for (int a = 1; a < len; a++) {
    for (int b = a+1; b < len; b++) {
        arr.add(getWord(s, a, b));
    }
}
Collections.sort(arr);	// 정렬
System.out.println(arr.get(0));	// 사전순으로 앞서는 단어 출력

 

 

코드 : github

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        String s = br.readLine();
        int len = s.length();
        List<String> arr = new ArrayList<>();
        for (int a = 1; a < len; a++) {
            for (int b = a+1; b < len; b++) {
                arr.add(getWord(s, a, b));
            }
        }
        Collections.sort(arr);
        System.out.println(arr.get(0));
    }

    private String getWord(final String s, final int a, final int b) {
        StringBuilder s1 = new StringBuilder(s.substring(0, a));
        StringBuilder s2 = new StringBuilder(s.substring(a, b));
        StringBuilder s3 = new StringBuilder(s.substring(b));
        StringBuilder sb = new StringBuilder();
        sb.append(s1.reverse()).append(s2.reverse()).append(s3.reverse());
        return sb.toString();
    }
}