문제 풀이

문자열 끝을 확인하면서 사전순으로 더 앞서는 문자를 추가해주는데, 만약 같은 문자가 나왔다면 더 깊게 파고들어서 사전순으로 앞서는 문자가 나오는쪽을 추가해주면된다.
만약 더 파고들었는데 문자가 양쪽 모두 같아서 결국 추가가 안됐다면 어느 한쪽이든 넣어주면된다.

문제 링크

boj/6137

소스코드

PS/6137.java

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		char[] arr = new char[N];
		char[] t = new char[N];
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().charAt(0);
		}

		int l = 0, r = N - 1, idx = 0;
		while (l <= r) {
			if (arr[l] < arr[r]) {
				t[idx++] = arr[l++];
			} else if (arr[l] > arr[r]) {
				t[idx++] = arr[r--];
			} else {
				int l2 = l, r2 = r;
				boolean flag =false;
				while (l2<=r2) {
					if (arr[l2] < arr[r2]) {
						flag =true;
						t[idx++] = arr[l++];
						break;
					} else if (arr[l2] > arr[r2]) {
						flag =true;
						t[idx++] = arr[r--];
						break;
					}
					else
					{
						l2++;
						r2--;
					}
				}
				if(!flag)
					t[idx++]=arr[l++];
			}
		}
		for(int i=0;i<N;i++) {
			bw.write(t[i]);
			if(i != 0 && (i+1) % 80 ==0)
				bw.write("\n");
		}
		bw.flush();
	}
}