풀이 아이디어

덱(Deque)을 사용해서 첫번째 문자열은 그냥 덱에 추가하고
그 뒤로 '덱의 첫번째 문자열'과 사전순으로 비교해서
더 빠르면 Deque.addFirst로 앞에 더하고, 더 느리거나 같으면 Deque.addLast로 더해준다.

배운 점

문자(Character) 비교

Character.compare(deque.getFirst(), currentCard) >= 0
Character.compare(a,b)함수는 문자를 사전순으로 비교해서
아스키코드 값이 더 크면 양수, 같으면 0, 작으면 음수를 반환한다.
즉 >=0이면 a가 크거나 같은경우 true를 반환한다.

Character 합치기: +연산자 vs StringBuilder

// 덱에 순서대로 문자열로 합침: +연산자
String result = "";
for(Character c: deque){
	result += c;
}

// 덱에 순서대로 문자열로 합침: StringBuilder
StringBuilder sb = new StringBuilder();
for(Character c: deque){
	sb.append(c);
}
String result = sb.toString();

왜 StringBuilder가 더 빠르고 메모리도 적게 먹을까?

위: +연산자 사용
아래: StringBuilder 사용

+연산자는 String 객체를 계속 새로 생성하는 방식으로 동작하지만
StringBuilder가 내부적으로 값을 바꿀 수 있는 문자열 버퍼를 사용해서 합치기 때문이다.

원래 자바에서 문자열(String)은 immutable로 값을 바꿀 수 없다.
문자열에 + 연산을 해도 사실 추가한 문자만 더하는게 아니라 그냥 새로운 String객체를
만들어서 String에 덮어쓰는 방식으로 동작한다.
하지만 StringBuilder는 내부적으로 문자 배열을 사용하고 문자를 추가할 때마다
새로운 객체를 생성하지 않고 기존 배열을 확장하는 방식으로 동작한다.

추가적인 String 객체생성을 하지 않아도 되기 때문에
문자를 하나의 문자열로 합칠 때, StringBuilder를 사용하면 메모리 사용량과 실행속도를 향상시킬 수 있다.

풀이 코드

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

public class _13417 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int i=0;i<t;i++){
            int n = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");
            Deque<Character> deque = new ArrayDeque<>();

            // 입력받은 문자열을 덱에 넣는다.
            for(int j=0;j<input.length;j++){
                // 첫번째는 그냥 더한다. 
                Character firstCard = input[j].charAt(0);
                if(j==0){
                    deque.add(firstCard);
                }
                // 두번째부터는 첫번째와 비교해서 더한다.
                else{
                    Character currentCard = input[j].charAt(0);
                    // 첫번째보다 작으면 왼쪽에 추가 
                    if(Character.compare(deque.getFirst(), currentCard) >= 0){
                        deque.addFirst(currentCard);
                        // System.out.println(deque);
                    }
                    // 크거나 같으면 오른쪽에 추가
                    else{
                        deque.addLast(currentCard);
                        // System.out.println(deque);
                    }
                }
            }

            // // 덱에 순서대로 문자열로 합침: +연산자
            // String result = "";
            // for(Character c: deque){
            //     result += c;
            // }

            // 덱에 순서대로 문자열로 합침: StringBuilder
            StringBuilder sb = new StringBuilder();
            for(Character c: deque){
                sb.append(c);
            }
            String result = sb.toString();

            System.out.println(result);
        }
    }
}