[BAEKJOON]13417 카드 문자열

문제 요약

• 알고리즘 분류: deque, 문자형, ASCII
• 난이도:  Silver3
• 문제내용:
  • 가장 처음에 가져온 카드는 자신의 앞에 놓는다.
  • 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 
  • N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

• 사이트: https://www.acmicpc.net/problem/13417

문제풀이

 이번 문제에서는 데크활용 하는 문제이다.

데크 자료구조는 앞뒤로 삽입, 삭제가 용이 하는 점에서 이용하면 앞에 문자보다 우선 순위가 크면 뒤로 추가 하고 작으면 앞으로 추가만 하면 된다.

 하지만 문자형은 단순하게 크기 비교 처리하기가 힘들다 그래서 ASCII 코드 값이 A-Z까지 순서로 번호가 지정 되어 있어서 그점을 활용해서 차이를 구해서 음수이면 앞에 양수이면 뒤에 붙이면된다. 자세한것은 아래 코드 보면된다.

Code

Python

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    alphas = list(input().split())
    d = deque(alphas[0])
    for alpha in alphas[1:]:
        # 문자 크기 비교
        # Character에서 덧쌤 뺄샘 할때 ASCII 코드 값으로 변환 해서 계산
        # 두 문자 뺄쌤해서 0이하이면 크기가 작으므로 앞에 붙인다.
        if(ord(alpha) - ord(d[0]) <= 0):
            d.appendleft(alpha)
        else:
            d.append(alpha)
    print(''.join(d))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++){
			int N = Integer.parseInt(br.readLine());
			Deque<Character> deque = new ArrayDeque<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			deque.add(st.nextToken().charAt(0));
			for (int j = 0; j < N - 1; j++) {
				char alpha = st.nextToken().charAt(0);
				// 문자 크기 비교
				// Character에서 덧쌤 뺄샘 할때 ASCII 코드 값으로 변환 해서 계산
				// 두 문자 뺄쌤해서 0이하이면 크기가 작으므로 앞에 붙인다.
				if(alpha - deque.peekFirst() <= 0){
					deque.addFirst(alpha);
				}else{
					deque.addLast(alpha);
				}
			}
			StringBuilder sb = new StringBuilder();
			deque.stream().forEach(data -> sb.append(data));
			System.out.println(sb.toString());
		}

	}
}