[백준_5430번] AC

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

5430번: 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만을 넘지 않는다.

 

[코드]

import java.util.*;

public class BaekJoon_5430 {
	static StringBuilder sb = new StringBuilder();
	static Scanner sc=new Scanner(System.in);
	static StringTokenizer st;
	public static void main(String[] args) {
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			String command=sc.next();
			int n=sc.nextInt();
			
			// [] 안에 입력받은 숫자들을 []와 , 구분자를 기준으로 분리한다.
			st=new StringTokenizer(sc.next(),"[],");
			ArrayDeque<Integer> deq=new ArrayDeque<>();
			
			// 덱에 분리한 숫자들을 삽입
			for(int i=0;i<n;i++)
				deq.add(Integer.parseInt(st.nextToken()));
			
			AC(command,deq);
		}
		System.out.println(sb);
	}
	
	// 
	public static void AC(String command, ArrayDeque<Integer> deq) {
		/*
		 * 현재 덱의 출력 위치가 덱의 앞인지 뒤인지 판별하는 변수
		 * true면 덱이 뒤집힌것 처럼 뒤쪽을 가리키고, false면 덱의 원래 상태인 앞을 가리킨다. 
		 */
		boolean reverse=false; 
		
		for(int i=0;i<command.length();i++) {
			char ch=command.charAt(i);
			
			// R 명령일 경우 : 배열에 있는 숫자의 순서를 뒤집는 함수
			if(ch=='R') {
				reverse=!reverse; 
				continue;
			}
			
			// D 명령일 경우 : 첫 번째 숫자를 버리는 함수
			else {
				// 숫자의 순서가 뒤집혀 있다면
				if(reverse==true) {
					/*
					 * 덱의 맨 뒷 숫자가 맨 앞 숫자가 되는 것이기 때문에
					 * pollLast() 함수로 덱의 맨 뒷 숫자를 제거한다. 
					 * 이때 덱에 제거할 수 있는 숫자가 없다면 error를 출력하고 종료한다.
					 */
					if(deq.pollLast()==null) {
						sb.append("error\n");
						return;
					}
				}
				// 숫자의 순서가 뒤집혀 있지 않다면
				else {
					/*
					 * 덱의 맨 앞 숫자를 제거하면 되기 때문에 
					 * pollFirst() 함수로 덱의 맨 앞 숫자를 제거한다. 
					 * 이때 덱에 제거할 수 있는 숫자가 없다면 error를 출력하고 종료한다.
					 */
					if(deq.pollFirst()==null) {
						sb.append("error\n");
						return;
					}
				}
			}
		}
		
		Print(deq,reverse);
	}
	
	// 연산이 끝난 결과를 출력하는 함수 
	public static void Print(ArrayDeque<Integer> deq, boolean reverse) {
		sb.append('['); // 괄호 시작
		
		// 덱에 숫자가 저장되어 있다면
		if(deq.size()>0) {
			// 배열이 뒤집혀 있는 경우 -> 덱의 뒤에서부터 출력
			if(reverse==true) {
				sb.append(deq.pollLast()); // 첫 번쨰 원소부터 저장
				
				// 다음 원소부터 콤마 뒤에 숫자를 붙여 출력
				while(!deq.isEmpty()) 
					sb.append(',').append(deq.pollLast());
			}
			// 배열이 뒤집혀 있지 않은 경우 -> 덱의 앞에서부터 출력
			else {
				sb.append(deq.pollFirst()); // 첫 번쨰 원소부터 저장
				
				// 다음 원소부터 콤마 뒤에 숫자를 붙여 출력
				while(!deq.isEmpty()) 
					sb.append(',').append(deq.pollFirst());
			}
		}
		sb.append(']').append('\n'); // 괄호 종료
	}
}

 

[고찰]

 이번 문제도 어떤 자료구조를 사용해야 효율적으로 문제를 풀 수 있을까 많은 고민을 해봤다. 특히 저장된 숫자를 뒤집는 부분에서 시간초과가 나지 않기 위해서는 배열을 사용해서는 안된다고 판단했다. 결론은 자료구조의 앞, 뒤에서 삽입/삭제가 가능한 덱을 사용하는 것이 가장 편리하다고 생각했다. 

 숫자를 뒤집었다면 덱의 뒷 원소부터 출력하고, 숫자를 뒤집지 않았다면 첫 번째 원소부터 출력하면 되기 때문에 해당 문제에서 가장 까다로운 부분을 쉽게 해결할 수 있었다. 그리고 괄호 안에 숫자가 저장된 것은 StringTokenizer를 사용하여 []와 , 를 분기점으로 제거하여 해결하였다. 이 두 부분 이외에는 어렵지 않게 코드를 짤 수 있었다. 

 

<문자열 라이브러리> StringTokenizer st=new StringTokenizer(문자열) : 띄어쓰기를 기준으로 문자열을 분리하는 함수 StringTokenizer st=new StringTokenizer(문자열, 구분자) : 구분자를 기준으로 문자열을 분리하는 함수 StringTokenizer st=new StringTokenizer(문자열, 구분자, true/false) : 구분자도 코든으로 넣을지(true), 구분자는 토큰에 포함을 시키지 않을지(false) 입력받아 구분자를 기준으로 문자열을 분리할 때