99클럽 코테 스터디 15일차 TIL 그리디(카드문자열)

https://www.acmicpc.net/problem/13417

 

<아이디어>

카드를 순서대로 하나씩 가져오면서 사전 순으로 가장 빠르게 정렬하는 것. 이때 가장 왼쪽 또는 가장 오른쪽에만 둘 수 있다.

핵심 아이디어는 문자를 하나씩 보면서 맨 앞 문자보다 순서가 빠르면 (아스키코드 값이 작으면) 맨 왼쪽에 두고,

맨 앞 문자보다 순서가 느리면 (아스키코드 값이 크면) 맨 왼쪽에 두어야 겠다고 생각했다.

그리고 자료구조는 Deque 또는 ArrayList 중에 고민하다가 후자를 택해 구현했다.

(Deque를 사용한다면 peekFirst와 addFirst / add 를 사용하면 된다)

 

<제출 코드>

package STUDY.Week03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Day15_BOJ_13417_카드문자열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        while(t --> 0){
            List<Character> list = new ArrayList<>();
            int n = Integer.parseInt(br.readLine());
            String[] str = br.readLine().split(" ");
            for(int i=0; i<n; i++){
                char ch = str[i].charAt(0);
                if(!list.isEmpty() && list.get(0) >= ch) list.add(0, ch);
                else list.add(ch);
            }
            for(char x : list) sb.append(x);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}