[Baekjoon] AC

👀 문제 설명

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

 

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

 

예제 입력 1

4

RDD

4

[1,2,3,4]

DD

1

[42]

RRD

6

[1,1,2,3,5,8]

D

0

[]

 

예제 출력 1

[2,1]

error

[1,2,3,,8]

error

 

✍🏻풀이

처음에는 단순하게 int 배열을 사용해서 하라는대로 구현했는데, 이렇게 할 경우 시간초과가 발생한다.

-> 테스트케이스는 최대 100이고, 배열의 수는 최대 100,000이기 때문에..

 

그래서 덱을 사용해서 푸니까 풀렸다!

먼저, [x1,..,xn] 형태로 배열에 들어있는 수를 arrStr에 입력받고, 대괄호를 모두 삭제해준다.

그리고 StringTokenizer을 사용해서 arrStr을 ","를 기준으로 분리시키고, 분리된 숫자들을 덱에 넣어준다.

 

덱에 숫자를 다 넣었으면, 순서를 저장하는 플래그 first를 사용해 현재 앞에서부터 삭제해야하는지, 뒤에서부터 삭제해야하는지를 표시한다.

그리고, 이 first에 따라 앞에서부터 숫자를 버려야하면, Deque.pollFirst로 삭제하고, 뒤에서부터 버려야하면, Deque.pollLast로 버린다.

이 때, 에러가 발생하면 "error"를 출력하고, 에러가 발생했는지 저장하는 변수 error를 true로 바꿔준다.

 

함수가 모두 실행되었다면, error 변수를 사용해 에러가 발생하지 않았는지 확인한다.

에러가 발생하지 않았다면, 배열에 든 숫자를 first에 따라 출력해주면 된다. (first가 true면 앞에서부터, false면 뒤에서부터 출력)

* 함수가 모두 실행되고, 에러가 발생하지 않았을 경우 + 배열에 숫자가 없을 때는 []를 출력해줘야 한다!

-> 처음에는 이걸 처리 안해서 틀렸다..!

 

코드

package boj;

// AC (https://www.acmicpc.net/problem/5430 )

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

public class BOJ_5430 {
	
	private static int T;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		// input
		T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			String p = br.readLine(); // 수행할 함수
			int n = Integer.parseInt(br.readLine()); // 배열에 들어있는 수의 개수
			// [x1, ..., xn] 형태로 배열에 들어있는 수를 입력받고,
			// 대괄호를 없앤다.
			String arrStr = br.readLine();
			arrStr = arrStr.replace("[", "");
			arrStr = arrStr.replace("]", "");
			// StringTokenizer로 ,를 기준으로 분리시켜준다.
			st = new StringTokenizer(arrStr, ",");
			
			// 덱을 사용해서 배열을 표현해준다.
			Deque<Integer> arr = new LinkedList<>(); // 함수를 수행하기 위해 덱 사용
			for (int i = 0; i < n; i++) {
				arr.push(Integer.parseInt(st.nextToken()));
			}
			
			// solve
			boolean error = false; // 에러가 났는지 확인해주기 위한 플래그
			boolean first = false; // 순서를 저장하는 플래그 (앞에서부턴지 뒤에서부턴지)
			for (int i = 0; i < p.length(); i++) {
				if (p.charAt(i) == 'R') { // R 이면 순서를 바꾼다.
					first = !first;
				}
				else if (p.charAt(i) == 'D') { // D 이면 덱에서 숫자를 버린다.
					// 배열이 비어있는데 D를 사용한 경우 에러 발생
					if (arr.size() == 0) {
						error = true;
						bw.write("error\n");
						break;
					}
					
					// 에러 발생하지 않았을 경우
					if (first) arr.pollFirst(); // 앞에서 숫자 버림
					else arr.pollLast(); // 뒤에서 숫자 버림
				}
			}
			
			// 에러가 발생하지 않고, 모든 함수가 수행되었을 경우
			if (!error) {
				// 에러가 발생하지 않고, 모든 함수가 수행된 후, 배열이 비어있을 때는 []를 출력해줘야 한다.
				if (arr.size() == 0) {
					bw.write("[]\n");
				}
				// 에러가 발생하지 않고, 배열에 숫자가 아직 있으면 배열 출력
				else {
					if (first) {
						bw.write("[");
						while (!arr.isEmpty()) {
							if (arr.size() == 1) bw.write(arr.pollFirst() + "]\n");
							else bw.write(arr.pollFirst() + ",");
						}
					}
					else {
						bw.write("[");
						while (!arr.isEmpty()) {
							if (arr.size() == 1) bw.write(arr.pollLast() + "]\n");
							else bw.write(arr.pollLast() + ",");
						}
					}
				}
			}
		}

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

}