#1251 : 단어 나누기

풀이방법

사용된 것:

브루트포스 알고리즘

 

2022.06.17

주어지는 문자열의 길이가 최대 50이므로, 단어를 쪼개는 두 지점을 고르는 경우의 수가 최대 50 곱하기 49 밖에 안 된다.

각 경우마다 쪼개고 뒤집는 과정을 수행하는 데에는 상수시간이 걸린다.

따라서 브루트포스 알고리즘으로 충분히 풀 수 있는 문제이다.

 

쪼개고 뒤집을 때는 String의 substring 메소드와 StringBuffer의 reverse 메소드를 사용했다.

 

이렇게 만들어낸 모든 문자열은 TreeSet에 저장하였고, TreeSet의 가장 앞에 있는 문자열을 화면에 출력하여 해결하였다.

 

코드

Java(2022.06.17)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		
		//쪼개고 뒤집은 결과물들을 저장할 트리셋
		TreeSet<String> ts = new TreeSet<String>();
		//가능한 모든 경우를 수행해보기
		int len = input.length();
		for(int i=1; i<len; i++) {
			for(int j=i+1; j<len; j++) {
				StringBuffer a = new StringBuffer(input.substring(0, i));
				StringBuffer b = new StringBuffer(input.substring(i, j));
				StringBuffer c = new StringBuffer(input.substring(j, len));
				ts.add(a.reverse().toString() + b.reverse().toString() + c.reverse().toString());
			}
		}
		//정답 출력
		System.out.print(ts.first());
	}

}