[TIL] 99클럽 코테 스터디 15일차 TIL + 백준 13417 카드 문자열

 

문제 풀이

 

문제 탐색하기

카드를 가져올 때 이미 가져와진 카드 더미의 왼쪽 또는 오른쪽으로 놓을 수 있습니다. 가져온 카드가 카드 더미의 첫 문자보다 사전 순으로 앞에 위치해야 할때는 왼쪽에 카드를 놓고 뒤에 위치해야하면 오른쪽에 카드를 놓으면 됩니다. 이 과정을 반복하면 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 만들 수 있습니다. 이렇게 매 순간 최적의 선택을 해서 해답을 구하는 그리디 알고리즘을 적용하여 풀 수 있었습니다.

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static Queue<Character> queue;
    static ArrayList<String> list = new ArrayList<>();

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

        StringTokenizer st;
        for(int i=0; i<T; i++){
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            queue = new LinkedList<>();
            for(int j=0; j<N; j++){
                queue.add(st.nextToken().charAt(0));
            }

            list.add(makeWord(queue));
        }

        for(String str : list){
            System.out.println(str);
        }
    }

    private static String makeWord(Queue queue){
        StringBuilder sb = new StringBuilder();
        sb.append(queue.poll());

        while(!queue.isEmpty()){
            char ch = (char) queue.poll();
            if(sb.charAt(0) >= ch){
                sb.insert(0, ch);
            }else{
                sb.append(ch);
            }
        }

        return sb.toString();
    }
}