[BOJ] 백준 5430번 AC (Java)

#5430 AC

난이도 : 골드 5

유형 : 구현

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

▸ 출력

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

 

문제 풀이  

조건 분기를 통해 각 케이스를 구현해주면 된다. 단, 연산의 최대 횟수는 10만, 배열 최대 크기는 10만이므로 효율적인 설계가 필요하다.

• 'R'연산은 직접적으로 자료구조를 변경시켜줄 필요없이 flag로 방향 정보만 기록해주면 된다.
• 'D'연산은 flag 방향 정보를 통해 앞 혹은 뒤에 있는 데이터를 제거해주면 된다. 이때 필요한 자료구조는 Stack과 Queue기능을 둘 다 가지고 있는 Deque이다. (만약 Deque가 비어있다면 "error"를 출력해주면 된다.)

 

풀이 코드 

마지막 결과 출력에 "\n"을 넣으면 50%에 실패가 발생하니 주의하자. 마지막에 "\n"을 빼주거나 println()으로 출력하면 문제없이 통과된다.

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while(tc-->0) {
			String op = br.readLine();
			int n = Integer.parseInt(br.readLine());
			String[] arr = br.readLine().replace("[", "").replace("]", "").split(",");
			sb.append(acFunction(op,n,arr));
			if(tc!=0) sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	static String acFunction(String op, int n, String[] arr) {
		Deque<Integer> q = new ArrayDeque<>();
		for(int i=0; i<n; i++) {
			q.offer(Integer.parseInt(arr[i]));
		}
		boolean dir = true; // true > , false <
		
		for(int i=0; i<op.length(); i++) {
			char type = op.charAt(i);
			if(type=='R') {
				dir = !dir;
			}
			else {
				if(q.isEmpty()) {
					return "error";
				}
				if(dir) { // >
					q.pollFirst();
				}else { // <
					q.pollLast();
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		while(!q.isEmpty()) {
			if(dir) {
				sb.append(q.poll());
			}else {
				sb.append(q.pollLast());
			}
			if(!q.isEmpty()) sb.append(",");
		}
		sb.append("]");
		return sb.toString();
	}
}