백준 13417 - 카드 문자열 (자바 - 그리디)

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

13417번: 카드 문자열

 

* 문제 요약

N 장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다.

가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그 다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다.

모든 카드를 다 가져온 후 자신의 앞에 놓인 카드를 순서대로 이어붙여 카드 문자열을 만들려고 한다.

 

예를 들어 3자의 카드가 M,K,U 순으로 놓여있다고 하자. 먼저 가장 왼쪽에 있는 M 이 적힌 카드를 가져와서 자신의 앞에 놓는다.

다음으로 남은 카드 중 가장 왼쪽에 있는 K 가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 U 가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 UKM 이라는 문자열을 만들 수 있다.

만약 K 가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 U 가 적힌 카드를 가져와서 가장 오른쪽에 두면 KMU 라는 문자열을 만들 수 있다. 이때 만들 수 있는 문자열 중 사전순으로 가장 빠른 문자열은 KMU 이다.

 

N 장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 만들 수 있는 카드 문자열 중 사전순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

 

* 입력

입력은 T 개의 테스트 데이터로 구성된다.

첫째 줄에 테스트 케이스의 갯수를 나타내는 자연수 T 가 주어진다.

각각의 테스트 케이스 첫째 줄에 처음에 놓여있는 카드의 갯수 N (1 <= N <= 1,000) 이 주어진다.

두 번째 줄에는 N 장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳 부터 순서대로 N 개가 공백으로 구분되어 주어진다.

모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다.

 

* 출력

입력받은 데이터에 대해, 한 줄에 1개씩 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력한다.

 

* 예시

 

* 해결 과정

입력받은 카드들을 가장 왼쪽에 있는 것 부터 가져와서 왼쪽 끝, 또는 오른쪽 끝에 놓는 방식으로 문자열을 만들어야 하므로 전체적으로 봤을 때 사전순으로 가장 앞서는 문자열을 만들어주기는 어렵다.

(입력된 글자 순서대로만 가져와야 하기 때문, 사전순으로 가장 빠른 문자열을 만들기 위해 아무데서나 카드를 가져올 수 는 없다.)

문제의 조건상 전체적으로 봤을 때 사전순으로 가장 앞서는 최적의 해를 구하기는 어려우므로 현재 상황 기준으로 가장 왼쪽에 있는 카드를 가져왔을 때 현재까지 만들어진 문자열에서 가장 왼쪽에 있는 글자와 비교하여 현재 가져온 카드가 사전순으로 더 앞서는 경우 문자열의 왼쪽 끝에 카드를 추가하고, 문자열의 가장 왼쪽에 있는 글자가 사전순으로 더 앞서는 경우 문자열의 오른쪽 끝에 카드를 추가해주는 방식으로 문제를 해결하였다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int i = 0; i < count; i++) {
            int size = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");

            Deque<Character> deque = new LinkedList<>();
            deque.offer(input[0].charAt(0));

            for (int j = 1; j < size; j++) {
                char ch = input[j].charAt(0);

                if (ch <= deque.peekFirst()) {
                    deque.offerFirst(ch);
                } else {
                    deque.offerLast(ch);
                }
            }

            StringBuilder sb = new StringBuilder();
            while (!deque.isEmpty()) {
                sb.append(deque.pollFirst());
            }

            bw.write(sb.toString() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

주어진 조건 안에서 사전순으로 최대한 앞서는 문자열을 만들기 위해 매 반복 단계마다 문자열의 가장 왼쪽에 있는 글자와 현재 가지고 온 카드의 글자를 비교해서 가져온 카드를 적절한 위치에 붙여가며 문자열을 만들었으므로 전체로서는 최적해라고 볼 수는 없으나, 각 단계별로 상황에 맞게 최적의 로직을 수행하는 그리디 알고리즘 문제라고 할 수 있다.