99클럽 코테 스터디 15일차 TIL (13417번: 카드 문자열)

문제

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

---

학습 키워드

• 그리디

 

풀이 및 코드

주어진 문자열의 맨 앞부터 문자를 차례대로 뽑으면서 빈 문자열부터 시작해, 만들고 있는 문자열의 왼쪽에 놓을지 혹은 오른쪽 끝에 놓을지 결정하는 문제이다. 

각 문자를 선택할 때마다 왼쪽 끝에 놓았을 때 완성되는 문자열과 오른쪽 끝에 놓았을 때 문자열을 비교해가면서 문자열 순서가 빠른 문자열로 완성해나가면 된다.

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		StringBuilder answer = new StringBuilder();
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());
			char[] arr = new char[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				arr[i] = st.nextToken().charAt(0);
			}
			answer.append(solution(arr, N) + "\n");
		}
		System.out.println(answer);
	}

	private static String solution(char[] arr, int N) {
		String answer = "";

		for (int i = 0; i < N; i++) {
			if ((answer + arr[i]).compareTo(arr[i] + answer) <= 0) {
				answer = answer + arr[i];
			} else {
				answer = arr[i] + answer;
			}
		}
		return answer;
	}
}