[백준] - 행운의 바퀴

행운의 바퀴

풀이

회전수와 회전했을 때 나오는 문자를 입력으로 받아, 최종적으로는 마지막 문자로부터 시계방향으로 출력하는 문제이다.
단 알 수 없는 문자는 "?"로 출력, 나올 수 없는 경우는 "!"를 출력한다.
나올 수 없는 경우는 다음과 같다.

1. 바퀴에서 같은 문자는 존재하지 않으므로, 같은 문자가 다른 위치에서 발견되었을 때
2. 바퀴의 같은 위치에서 다른 문자가 나올 때

이 경우는 "!"를 출력한다.

양 끝에서 삽입과 제거가 가능할 수 있는 LinkedList 자료구조를 사용하였다.
회전 수 만큼 앞쪽에서 빼서 뒤쪽으로 넣어주고, 가장 앞에 있는 문자를 비교하여 "?"일 경우에는 입력의 문자를 넣어주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력 값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        LinkedList<String> list = new LinkedList<>();
        boolean[] checked = new boolean[26];

        for(int i = 0; i < N; i++){
            list.add("?");
        }
        String answer = "";
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            String alpha = st.nextToken();

            for(int j = 0; j < cnt; j++){
                list.addLast(list.removeFirst());
            }

            String str = list.removeFirst();
            int idx = 'Z' - alpha.charAt(0);
            // 같은 알파벳은 다시 나올 수 없다.
            if("?".equals(str) && checked[idx]){
                answer = "!";
                break;
            }
            // ?이거나, 같은 위치의 같은 알파벳이라면 가능하다
            else if("?".equals(str) || str.equals(alpha)){
                list.addFirst(alpha);
                checked[idx] = true;
            }
            // 같은 위치에서는 다른 알파벳이 나올 수 없다.
            else if(!str.equals(alpha)){
                answer = "!";
                break;
            }
        }

		/*
      		시계방향으로 출력하는데 linkedlist의 가장 앞과 끝을 잇는다고 
            생각하면 현재 가리키는 문자는 idx가 0인 원소이다
            이때 한바퀴 돌린다면 다음 가리키는 원소는 linkedlist 사이즈의 - 1에 
            해당하는 원소이므로 가장 뒤에 있는 원소부터 차례대로 출력된다.
        */
        if("".equals(answer)){
            list.addLast(list.removeFirst());
            while(!list.isEmpty()){
                answer += list.removeLast();
            }
        }

        System.out.println(answer);
    }
}