2993번: 세 부분

문제 출처 : https://www.acmicpc.net/problem/2993

 

언어 : Kotlin

 

문제 설명 :

독서를 싫어하는 원섭이는 책에서 단어 하나를 임의로 선택한다. 그 다음, 단어를 세 부분으로 나눈다.

세 부분으로 나눈 단어를 각각 순서를 뒤집는다. (첫 번째 글자와 마지막 글자의 위치를 바꾸고, 두 번째 위치와 뒤에서 두 번째 글자의 위치를 바꾸고... 이런 식으로 계속)

마지막으로, 이 세 단어를 나누기 전과 같은 순서로 합쳐 하나로 만든다.

원섭이는 사전순으로 가장 앞서는 단어를 만들려고 한다. 원섭이가 고른 단어가 주어졌을 때, 만들 수 있는 단어 중 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 원섭이가 고른 단어가 주어진다. 고른 단어는 알파벳 소문자로 이루어져 있고, 길이는 3보다 크거나 같고, 50보다 작거나 같다.

 

출력 :

첫째 줄에 원섭이가 만들 수 있는 단어 중 사전순으로 가장 앞서는 단어를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
dcbagfekjih	abcdefghijk
mobitel	bometil
anakonda	aanadnok

 

풀이 : 

문자를 세 부분으로 나눠야한다.

세 부분으로 나뉠려면 한 부분당 최소 1개의 문자는 들어가 있어야 한다.

 

이를 토대로 반복문을 짠다.

0 ~ word.lastIndex - 1

i + 1 ~ word.lastIndex

이렇게 중첩 반복문을 구성하면 세 부분으로 나눌 수 있다.

 

위의 내용을 예제 1로 예를 들면 다음과 같다.

	0	1	2	3	4	5	6	7	8	9	10
0 ~ word.lastIndex - 1	d	c	b	a	g	f	e	k	j	i
i + 1 ~ word.lastIndex											h

 

이 상태에서 3개로 나눌 수 있게 된다.

 

	0	1	2	3	4	5	6	7	8	9	10
replace 1	d
replace 2		c	b
replace 3				a	g	f	e	k	j	i	h

 

이것을 문제에서 지시한대로 reversed() 시키며 반복문을 통하면 다음과 같이 나온다.

d c hijkefgab
d bc hijkefga
d abc hijkefg
d gabc hijkef
d fgabc hijke
d efgabc hijk
d kefgabc hij
d jkefgabc hi
d ijkefgabc h
cd b hijkefga
cd ab hijkefg
cd gab hijkef
cd fgab hijke
cd efgab hijk
cd kefgab hij
cd jkefgab hi
cd ijkefgab h
bcd a hijkefg
bcd ga hijkef
bcd fga hijke
bcd efga hijk
bcd kefga hij
bcd jkefga hi
bcd ijkefga h
abcd g hijkef
abcd fg hijke
abcd efg hijk
abcd kefg hij
abcd jkefg hi
abcd ijkefg h
gabcd f hijke
gabcd ef hijk
gabcd kef hij
gabcd jkef hi
gabcd ijkef h
fgabcd e hijk
fgabcd ke hij
fgabcd jke hi
fgabcd ijke h
efgabcd k hij
efgabcd jk hi
efgabcd ijk h
kefgabcd j hi
kefgabcd ij h
jkefgabcd i h

 

이렇게 나오는 단어를 합치고 result와 min으로 비교하여 더 작은(사전순으로 빠른) 값을 도출하면 된다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val word = readLine()
    var result = word

    for (i in 0 until word.lastIndex - 1) {
        for (j in i + 1 until word.lastIndex) {
            val cur = StringBuilder(word)

            cur.replace(0, i + 1, cur.substring(0, i + 1).reversed())
            cur.replace(i + 1, j + 1, cur.substring(i + 1, j + 1).reversed())
            cur.replace(j + 1, word.length, cur.substring(j + 1, word.length).reversed())
            result = minOf(cur.toString(), result)
        }
    }
    
    bw.write(result)
    bw.flush()
    bw.close()
}