BOJ_1251 [ 단어 나누기 ]

문제

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

 

 

 

문제 해결 방법

 

문제에서 주어진 조건으로 단어를 입력 받았을 때

세 등분으로 나눠서 각각 나눈 단어들을 뒤집어서 합친 단어가 사전순으로 가장 앞서는 것을 출력하는 문제입니다.

 

세 등분을 나눌 때 문제에서 단어길이가 최소 1이므로 (단어 처음인덱스를 0으로 가정하겠습니다.)

인덱스로 나눈다고 했을 때

단어에서 처음에 나눌 수 있는 범위는 0부터 (단어길이-2)  만큼 나눌 수 있으며  

두번째 나눌 수 있는 i(처음 나눈 마지막 인덱스 값)+1 부터 (단어 길이 -1) 만큼 나눌 수 있고

마지막으로 j(두번째 나눈 마지막 인덱스 값)+1 부터 (단어 길이)만큼  나눌 수 있습니다.

 

글로 보면 어려울 수 있으므로 아래 그림으로 설명 드리겠습니다.

badewqa 라는 단어가 주어졌을 때 각 알파벳마다 인덱스는 아래 표와 같이 가졌다면,

 

인덱스	0	1	2	3	4	5	6
단어	b	a	d	e	w	q	a

 

첫번째로 나눌 수 있는 인덱스 범위는 0- 4 까지이며 

두번째로 나눌 수 있는 인덱스 범위는 (i+1) - 5 까지   (i는 첫번째로 나눈 마지막 인덱스 값)

세번째로 나눌 수 있는 인덱스 범위는 (j+1) - 6 까지 입니다. (j는 두번째로 나눈 마지막 인덱스 값)

 

모든 경우의 수를 구해서 사전 순이 앞에 있는 것을 찾아내면 됩니다.

 

 

소스 코드

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/Brute%20force/Main.java