[Baekjoon] 백준 13417번: 카드 문자열 (JAVA)

문제 13417

13417번: 카드 문자열

 

[ 문제 풀이 ]

입력받은 순서대로 문자를 가져와서 적절하게 배치하여 사전 순으로 가장 빠른 문자열을 만들어야 합니다. 문제에서 나온 조건대로 도식화하면 아래와 같습니다.

 

 

문자열의 맨 앞의 문자와 맨 뒤의 문자를 각각 저장하기 위한 변수를 만들고, 맨 앞과 맨 뒤에 배치하기 위해 Deque을 사용하였습니다.

[ 코드 ]

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

public class Main {
    private static Queue<String> cards = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                cards.offer(st.nextToken());
            }

            Deque<String> result = new LinkedList<>();
            String first = cards.poll(); // 첫 글자
            String last = first; // 마지막 글자
            result.offer(first);
            while (!cards.isEmpty()) {
                String str = cards.poll();
                if (first.compareTo(str) >= 0) { // first 보다 작거나 같으면 first 업데이트
                    first = str;
                    result.addFirst(first);
                } else { // last 업데이트
                    last = str;
                    result.addLast(last);
                }
            }

            while (!result.isEmpty()) {
                bw.write(result.poll());
            }
            bw.newLine();
            bw.flush();
        }
    }
}