[BOJ 6137] 문자열 생성

문제

• BOJ 6137
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

문자열을 받아서 맨 앞인덱스와 맨뒤 인덱스부터 시작해서 사전순 더 빠른 알파벳이 있으면 ans에 넣고 만약에 같으면 둘 중 선택했을 때 사전순으로 더 빠른 알파벳이 나오는 경우, 그 인덱스쪽을 선택해 ans에 넣는다. 이렇게 문자열 ans를 만들면서 개수를 세서 80개씩 만들어질 때 줄바꿈한다.

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

//문자열 생성
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static char[] arr;
	static int N;
	static StringBuilder ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		N =  Integer.parseInt(br.readLine());
		arr = new char[N];
		ans = new StringBuilder();
		
		for(int i=0; i<N; i++) {
			arr[i] = br.readLine().charAt(0);
		}//End input
		
		int si = 0, ei = N-1; 
		int cnt = 0;
		while(si<=ei) {
			int result = Character.compare(arr[si], arr[ei]); //앞, 뒤 문자 비교
			if(result > 0) ans.append(arr[ei--]); //앞이 더 큼 = 뒤가 더 빠름
			else if(result < 0) ans.append(arr[si++]); //앞이 더 빠름
			else { //같을 때
				int fi = si, bi = ei;
				
				while(arr[fi] == arr[bi]) { //가운데로 가면서 더 빠른 알파벳이 나오는 경우 찾기
					if(bi > 0) bi--;
					if(fi < N-1) fi++;
					
					int res = Character.compare(arr[fi], arr[bi]);
					if(res > 0) { //뒤를 선택해서 더 빠른 알파벳이 나올 때
						ans.append(arr[ei--]);
						break;
					}else if(res < 0) {
						ans.append(arr[si++]);
						break;
					}
				}
			}
			
			if(++cnt % 80 == 0) ans.append("\n");
		}
		
		System.out.println(ans.toString());
	}
}