티스토리 뷰
[JAVA] 백준 #5430 AC
https://www.acmicpc.net/problem/5430
🔒 문제
선영이는 주말에 할 일이 없어서 새로운 언어 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를 출력한다.
🔎 풀이
배열도 사용해 보고, ArrayList도 사용해 보고 몇 시간 동안 헤맸는데 이 문제를 관통하는 최적의 자료구조는 덱(Deque)이다.
여기서 포인트는 [1] 뒤집기 명령어가 나와도 자료 구조 자체를 뒤집으면 시간 초과가 발생한다. [2] 덱을 사용하면 삭제를 가장 빠르게 구현할 수 있다(O(1))
그럼 첫 번째부터 자세히 살펴보자. 자료를 직접 뒤집지 않으면 대체 어떻게 결과를 낸다는 말인가? ➡️ boolean 타입의 reverse 플래그를 사용해서 false면 출력할 때 원래 순서대로, true면 맨 뒤 인덱스부터 역순으로 출력하면 된다.
만약 배열이나 데크를 뒤집으려면 시간 복잡도는 O(n)이 소요되는데 이렇게 불 타입 변수를 활용해서 배열 자체를 뒤집은 듯한 효과를 내는 것이다!
그럼 여기서 드는 의문이 있다. 뒤집은 다음에 삭제하는 경우는 어떻게 처리할 것인가? ➡️ 여기서 Deque이 엄청난 장점을 발휘한다. 마찬가지로 reverse 플래그 값이 true면 뒤집은 상태라는 뜻이니까 맨 뒤에 있는 요소를 삭제한다. ( 맨 뒤 요소가 현재 뒤집은 상태였다면 맨 첫 번째 요소일 테니까 ) 덱은 pollFirst, pollLast와 같이 맨 앞 요소와 맨 뒤 요소를 삭제할 때 시간 복잡도가 단 O(1)에 불과하는 효과적인 메서드를 제공한다. 이것을 활용해서 효과적으로 구현할 수 있다.
🔹 전체 코드
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int T;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(bf.readLine());
for( int i = 0; i<T; i++ ){
String s = bf.readLine();
int N = Integer.parseInt(bf.readLine());
String input = bf.readLine();
Deque<Integer> deque = new LinkedList<>();
if( N == 0 ){
if(s.contains("D")) System.out.println("error");
else System.out.println("[]");
continue;
}
for( int j = 1; j < input.length(); j++ ){
StringBuilder number = new StringBuilder();
while (input.charAt(j) != ',' && input.charAt(j) != ']') {
number.append(input.charAt(j));
j++;
}
deque.offer(Integer.parseInt(number.toString()));
}
boolean error = false;
boolean reverse = false;
for( int j = 0; j<s.length(); j++ ){
if( s.charAt(j)=='R'){ // 뒤집기
reverse = !reverse;
}
else{
if(deque.isEmpty()) error = true;
if(!reverse) deque.pollFirst();
else deque.pollLast();
}
}
if(error) System.out.println("error");
else{
System.out.print("[");
StringBuilder result = new StringBuilder();
if(!reverse){
while(!deque.isEmpty()){
result.append(deque.pollFirst()).append(",");
}
}
else {
while(!deque.isEmpty()){
result.append(deque.pollLast()).append(",");
}
}
if(result.length()>0) result.deleteCharAt(result.length()-1);
System.out.print(result);
System.out.println("]");
}
}
}// end of main
}// end of class