6137번: 문자열 생성

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

 

언어 : Kotlin

 

문제 설명 :

N개의 문자로 이루어진 문자열 S가 입력된다.
이 문자열의 각 문자들로 새로운 문자열 T를 만들려고한다.
문자열 S로 문자열 T를 만드는 규칙은 다음과 같다.

• 문자열 S의 가장 앞의 문자 하나를 문자열 T의 마지막에 추가한다.
• 문자열 S의 가장 뒤의 문자 하나를 문자열 T의 마지막에 추가한다.

위 규칙으로 만들어진 문자열 T들 중 사전순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

 

입력 :

첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 2,000)
이후 N개의 줄에 S를 이루는 문자들이 주어진다.

 

출력 :

만들어진 사전순으로 가장 빠른 문자열을 출력한다. 80글자마다 새줄 문자를 출력해야 한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
6 A C D B C B	ABCBCD

 

풀이 : 

주어진 문자열의 시작과 끝에서 투포인트로 그리드 알고리즘을 시행한다.

문자열[시작]과 문자열[끝]을 비교하여 아스키 코드가 더 작은 문자를 문자열 T에 추가한다.

시작은 증감하고 끝은 감소한다

 

만약 시작 = 끝이 같을 경우, 시작 + 1과 끝 - 1을 비교한다

비교했는데 비교한 알파벳이 같다면 같지 않을때까지 비교한다

 

시작 > 끝이 되면 프로그램은 종료한다.

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 n = readLine().toInt()
    val arr = CharArray(n) { readLine()[0] }
    val result = ArrayList<Char>()

    val index = IntArray(2).also { it[1] = n - 1 }
    while (index[0] <= index[1]) {
        if (arr[index[0]] < arr[index[1]]) {
            result.add(arr[index[0]++])
        } else if (arr[index[0]] == arr[index[1]]) {
            val tempIndex = IntArray(2).also {
                it[0] = index[0]
                it[1] = index[1]
            }
            var check = true

            while (arr[tempIndex[0]] == arr[tempIndex[1]]) {
                if (tempIndex[1] > 0) tempIndex[1]--
                if (tempIndex[0] < n - 1) tempIndex[0]++

                if (arr[tempIndex[0]] < arr[tempIndex[1]]) check = true
                else if (arr[tempIndex[0]] > arr[tempIndex[1]]) check = false
            }

            if (check) result.add(arr[index[0]++]) else result.add(arr[index[1]--])
        } else {
            result.add(arr[index[1]--])
        }
    }

    result.chunked(80).forEach {
        bw.appendLine(it.joinToString(""))
    }
    bw.flush()
    bw.close()
}