6137 백준 문자열 생성

N개의 문자로 이루어진 문자열 S가 입력된다.

이 문자열의 각 문자들로 새로운 문자열 T를 만들려고한다.

문자열 S로 문자열 T를 만드는 규칙은 다음과 같다.

문자열 S의 가장 앞의 문자 하나를 문자열 T의 마지막에 추가한다.
문자열 S의 가장 뒤의 문자 하나를 문자열 T의 마지막에 추가한다.
위 규칙으로 만들어진 문자열 T들 중 사전순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력
첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 2,000)

이후 N개의 줄에 S를 이루는 문자들이 주어진다.

S의 어떤 문자를 T에 넣을 것인가? 가 중요 문제였다
넣는 방법은 두가지 방법이 있는데
가장 앞의 문자를 넣거나 가장 뒤의 문자를 넣는 방법이다.

1. 두 개의 문자가 다를 때는 문자의 아스키 코드가 작은 것을 넣으면 된다
2. 같을 때는 가장 가까운 문자가 더 작은 쪽을 먼저 넣으면
된다.

Java Code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        char arr[] = new char[N];
        for(int i = 0; i < N; i++) {
            arr[i] = br.readLine().charAt(0);
        }
        int left = 0;
        int right = N - 1;
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        while(left <= right) {
            if(cnt != 0 && cnt % 80 == 0) {
                sb.append("\n");
            }

            if(arr[left] < arr[right]) {
                sb.append(arr[left]);
                left++;
                cnt++;
            } else if(arr[left] > arr[right]) {
                sb.append(arr[right]);
                right--;
                cnt++;
            } else {
                if(check(arr, left + 1, right - 1)) {
                    sb.append(arr[left]);
                    left++;
                    cnt++;
                } else {
                    sb.append(arr[right]);
                    right--;
                    cnt++;
                }
            }



        }
        System.out.println(sb);

    }
    static boolean check(char arr[], int l, int r) {
        while(l < r) {
            if(arr[l] < arr[r]) {
                return true;
            } else if(arr[l] > arr[r]) {
                return false;
            }
            l++;
            r--;
        }

        return false;
    }
}

Python Code

def start():
    N = int(input())
    arr = []
    for _ in range(N):
        M = input()
        arr.append(M)
    left = 0
    right = len(arr) - 1
    str = ""
    cnt = 0
    while left < right:
        if cnt != 0 and cnt % 80 == 0:
            str += '\n'
        cnt += 1
        if arr[left] == arr[right]:
            inLeft = left + 1
            inRight = right - 1
            flag = False
            while(inLeft < inRight):
                if arr[inLeft] != arr[inRight]:
                    if arr[inLeft] > arr[inRight]:
                        str += arr[right]
                        right -= 1
                        flag = True
                        break
                    else:
                        str += arr[left]
                        left += 1
                        flag = True
                        break
                inLeft += 1
                inRight -= 1
            if flag is False:
                str += arr[left]
                left += 1

        else:
            if arr[left] > arr[right]:
                str += arr[right]
                right -= 1
            else:
                str += arr[left]
                left += 1
    print(str + arr[left]);



if __name__ == '__main__':
    start()