문제

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

풀이

이 문제는 그림으로 보면 설명이 쉽다. 원판으로 설명하였지만, 사실 위처럼 연결리스트로 놓고 고민하는 것이 편할 수도 있다.

가장 중요한 요점은 알파벳을 넣으려고 할 때의 조건인데

C를 넣으려고 할때 그 공간은 비어있거나 또는 C 만 허용한다.
나는 빈 공간을 ?로 채워넣어서 내 예제로 설명을 하면
A를 넣으려고 한다면 ? 이거나 넣으려는 알파벳과 같은 A만이 가능하다는 뜻이다.

또 중요한 조건이 하나 더 있는데
C를 넣으려고 할때 다른 곳에 C가 있으면 안된다.
즉, 알파벳은 각자 하나씩만 부여가능하다는 것이다.

또 주의해야하는 것이 있는데

출력방향과 입력방향이 반대라는 것을 기억하여

입력한 방향과 반대로 출력을 해야한다는 점이 있다.

하지만, 이 부분은 직접 로직을 만들고 출력을 해보면 금방 발견할 수 있는 부분이다.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Num2840 {

    public static int N;
    public static int K;
    public static int S1[];
    public static String S2[];
    public static Deque<String> deque = new ArrayDeque<>();

    public static int[] alpha = new int[27];

    public static void main(String[] args) {
        //input
        Scanner scanner = new Scanner(System.in);
        String[] a = scanner.nextLine().split(" ");
        N = Integer.parseInt(a[0]);
        K = Integer.parseInt(a[1]);
        S1 = new int[K];
        S2 = new String[K];
        for (int i=0; i<K; i++) {
            a = scanner.nextLine().split(" ");
            S1[i] = Integer.parseInt(a[0]);
            S2[i] = a[1];
        }
        for (int i=0; i<N; i++) {
            deque.addLast("?");
        }

        //logic
        for (int i=0; i<K; i++) {
            for (int j=0; j<S1[i]; j++) {
                deque.addLast(deque.pollFirst());
            }
            if (!deque.peek().equals("?") && !deque.peek().equals(S2[i]) ||
                    deque.peek().equals("?") && alpha[S2[i].charAt(0)-'A'] == 1) {
                System.out.println("!");
                return;
            } else {
                deque.pollFirst();
                deque.addFirst(S2[i]);
                alpha[S2[i].charAt(0)-'A'] = 1;
            }
        }
        deque.addLast(deque.pollFirst());

        //output
        for (int i=0; i<N; i++) {
            System.out.print(deque.pollLast());
        }
        System.out.println();
    }
}