[백준] 13417 카드 문자열 - 그리디(Greedy, 탐욕법) JAVA

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

코드설명

그리디(Greedy, 탐욕법) 문제입니다.

 

사전순으로 가장 빠르게 작성하려면, 항상 맨 앞의 숫자를 기준으로 처리합니다. 

즉, 각 단계에서 현재 가능한 최선의 선택을 하는 그리디 접근법을 사용합니다. 매 순간 사전순으로 가장 작은 문자열을 만들기 위해 노력하며, 이전의 선택을 번복하지 않습니다.

 

이 문제에서는, 가장 맨 앞의 글자를 기준으로 맨 앞의 글자가 사전순으로 더 빠르다면 맨 뒤에 붙이고, 아니라면 맨 앞에 붙입니다.

 

문제에서 this.Character.compareTo(Other.Character) 를 활용하여 손쉽게 로직을 구현했습니다.

만약 (this.Character의 사전순) > (other.Character의 사전순) 이라면 양수를 반환합니다. 즉, this.Character가 사전순으로 더 뒤에 있음을 의미하니, other.Character를 맨 앞에 붙여야 합니다.

== 0 인경우,  < 0 (음수인경우) 도 같이 생각하면 됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, K, M, L;
    private static int[] arr;
    private static int answer = 0;
    private static ArrayList<Character> arrList = new ArrayList<>();
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			arrList.clear();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				Character input = st.nextToken().charAt(0); 
				
				if(i==0) {
					arrList.add(input);
					continue;
				}
				
				//만약 this.character가 other.character보다 더 작다면, 사전순으로 앞서다면 other은 뒤에 붙인다.
				if(arrList.get(0).compareTo(input) < 0) {
					arrList.add(arrList.size(), input);
				}else if(arrList.get(0).compareTo(input) == 0) {
					arrList.add(0, input);
				}else if(arrList.get(0).compareTo(input) > 0) {
					arrList.add(0, input);
				}
				
			}
			for(Character v : arrList) {
				System.out.print(v);
			}
			System.out.println();
			
//			System.out.println(arrList.toString());
		}
    }
    
    
}