https://www.acmicpc.net/problem/5430
1. 문제 요약
AC는 정수 배열에 연산을 수행하는 언어로, R(뒤집기)와 D(버리기)라는 두 가지 함수로 구성된다.
R은 배열의 순서를 뒤집는 함수이다.
D는 배열의 첫 번째 수를 버리는 함수이다. 만약 빈 배열에 D를 수행하면 에러가 발생한다.
이러한 함수들을 조합해서 여러 번 사용할 수 있다.
에러가 발생하면 error를 출력한다.
테스트 케이스 수 T는 최대 100
수행할 함수의 개수 p는 최대 10만
배열의 길이 n은 최대 10만
배열 원소의 값은 최대 100
전체 테스트 케이스에서 p의 합과 n의 합은 70만을 넘지 않는다.
2. 문제 접근
문제를 어떻게 해결해야 할지 고민해야 한다. 지우기 함수의 작동 방식을 고려하면 ArrayDeque로 배열을 구성하면 될 것 같다.
다만 뒤집기 함수가 시간복잡도 관점에서 장애가 될 수 있다. 뒤집기를 한 번 수행하면 이 필요하지만, 함수의 개수도 최대 10만이기 때문에 뒤집기 연산만 수행한다면 되어 시간복잡도를 넘게 된다.
양쪽 끝에서 삽입과 삭제가 가능하다는 덱의 특성을 이용하면 이러한 문제를 해결할 수 있다. 뒤집기 연산은 실제로 수행하지 않고, 뒤집어진 상황에서 버리기 연산을 수행할 때는 배열 맨 뒤의 값을 버리면 된다.
3. 풀이
기본적인 아이디어는 다음과 같다.
- 각 테스트 케이스에 대해 다음을 수행한다.
- 입력 배열을 받고 숫자만 남겨 덱에 넣는다.
- 명령 문자열을 훑으며 함수를 수행한다.
3.1. 뒤집는 연산인 경우 뒤집기 여부를 갱신한다.
3.2. 버리기 연산인 경우 뒤집기 여부를 고려하여 값을 버린다. 만약 배열이 비어있다면 에러를 발생시킨다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 테스트 케이스 수 입력 받기
int T = Integer.parseInt(br.readLine());
// 각 테스트 케이스에 대해 수행
for (int tc = 0; tc < T; tc++) {
String p = br.readLine(); // 수행할 함수의 문자열
int n = Integer.parseInt(br.readLine()); // 입력받을 배열의 길이
// 배열 입력 받기
String numsArray = br.readLine();
// 첫 글자와 마지막 글자를 지워서 대괄호를 없앤다.
String[] nums = numsArray.substring(1, numsArray.length()-1).split(",");
// 덱 선언
ArrayDeque<Integer> arr = new ArrayDeque<>();
// 입력 받은 배열의 값을 덱에 넣기
for (int i = 0; i < n; i++) {
arr.add(Integer.parseInt(nums[i]));
}
int orderNum = p.length(); // 명령 개수
boolean isReverse = false; // 순서를 뒤집는 상황인지 판단
boolean isError = false; // 에러인 경우 판단
// 명령 문자열을 훑으며 함수 수행
for (int i = 0; i < orderNum; i++) {
// 뒤집는 명령인 경우
if (p.charAt(i) == 'R') {
isReverse = !isReverse;
}
// 첫번째 문자 삭제 명령인 경우
else {
// 배열의 현 길이가 0이라면 에러 발생하고 루프 끝냄
if (arr.isEmpty()) {
isError = true;
break;
}
// 순서를 뒤집지 않는 경우 앞에서 지움
if (!isReverse) {
arr.removeFirst();
}
// 순서를 뒤집는 경우 뒤에서 지움
else {
arr.removeLast();
}
}
}
// 결과 추가하기
// 에러라면 error추가
if (isError) {
sb.append("error\n");
}
// 에러가 아니라면 형식에 맞춰 추가
else {
sb.append("[");
// 길이가 0이 아닌 경우일 때
if (!arr.isEmpty()) {
// 뒤집지 않는 경우 앞에서부터
if (!isReverse) {
while (!arr.isEmpty()) {
sb.append(arr.removeFirst());
sb.append(",");
}
// 마지막 콤마 지우기
sb.deleteCharAt(sb.length()-1);
}
// 뒤집는 경우라면 뒤에서부터
else {
while (!arr.isEmpty()) {
sb.append(arr.removeLast());
sb.append(",");
}
// 마지막 콤마 지우기
sb.deleteCharAt(sb.length()-1);
}
}
sb.append("]\n");
}
}
// 정답 출력
System.out.println(sb);
}
}4. 회고
이 문제에서는 문제 해결 방법보다 생소한 입력 형태에서 숫자 배열을 얻는 것이 가장 큰 문제였다.... 최종적으로는 substring 메서드를 사용해서 괄호를 제거하고, split 메서드를 사용해 콤마로 구분된 숫자를 얻었다.
틀렸던 이유: 배열의 길이가 0인데 R만 하는 경우는 에러가 발생하지 않으며, 빈 배열이 그대로 나와야 한다.
