https://www.acmicpc.net/problem/5430
5430번: AC
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
www.acmicpc.net
문제
선영이는 주말에 할 일이 없어서 새로운 언어 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를 출력한다.
이 문제를 보고 처음 든 생각은 "덱을 사용하자!!"
하지만 주요 핵심을 파악하지는 못했다..
문제 그대로 구현했다가 시간초과가 났다.
R일 때마다 계속 순서를 뒤집어주니까 시간초과가 났다.
이 문제를 풀면서 중간중간 오류들이 많았으며 그만큼 배운 것도 많았기에 하나씩 적어볼 것이다!
그럼 시작!
[x1,...,xn] 를 입력받는 것 부터 난관이었다.
괄호, 쉼표를 제외하고 숫자만 뽑아서 덱에 넣고 싶었다.
substring으로 괄호를 자르고, split으로 쉼표로 구분하면 된다.
String[] nums = str.substring(1, str.length() - 1).split(",");
구한 숫자들을 deque에 넣어준다.
for (int i = 0; i < n; i++) {
deque.add(nums[i]);
}
이제는 AC명령어 R, D에 따라 함수를 구현해주면 된다.
R이 나왔을 때, 순서를 굳이 뒤집지 않고, 시작 방향만 지정해준다.
isLeft 변수를 선언하여 왼쪽이 시작인지 오른쪽이 시작인지 정해준다.
R이 나올 때마다, isLeft를 반대로 설정해주면된다.
if (command == 'R') {
isLeft = !isLeft;
}
그럼 D가 나왔을 때는, isLeft에 따라서 삭제를 해주면 된다.
isLeft == true 이면, 앞에서 삭제
isLeft == false 이면, 뒤에서 삭제
if (isLeft) {
deque.pollFirst();
} else
deque.pollLast();
그리고 문제에서 빈 배열이면서 D를 사용한 경우에는 error를 출력하도록 했다.
flag형태로 deque이 비었을 경우 false를 리턴하여, false이면 error를 출력하도록 했다.
if (deque.isEmpty()) {
return false;
}
이제 출력 양식에 맞춰 출력해주면 된다.
빈 배열일 경우에는 error를 출력하도록 했으므로, 빈 배열이 아닐 경우만 생각하여 구현했는데, 착각이었다.빈 배열일 경우가 아닌, 빈 배열이면서 D를 사용한 경우에 error출력이다.
즉, 배열에 값이 하나가 있을 때, D를 통해 삭제되어 빈 문자열이 된 경우에는 빈 문자열 [] 를 출력해야 한다.
deque이 빈 배열이든 아니든 상관없이 sb.append("["); 로 시작해야 한다.
그리고 isLeft의 상태에 따라 출력해주면 된다.
isLeft == true 이면 앞에서부터 출력
isLeft == false 이면 뒤에서부터 출력
b.append("[");
if (!deque.isEmpty()) {
if (isLeft) {
sb.append(deque.pollFirst());
while(!deque.isEmpty()){
sb.append("," + deque.pollFirst());
}
} else{
sb.append(deque.pollLast());
while(!deque.isEmpty()){
sb.append("," + deque.pollLast());
}
}
}
sb.append("]").append("\n");
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static StringBuilder sb = new StringBuilder();
static Deque<String> deque = new ArrayDeque<>();
static char[] p;
static boolean isLeft = true;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
p = br.readLine().toCharArray();
int n = Integer.parseInt(br.readLine());
String str = br.readLine();
String[] nums = str.substring(1, str.length() - 1).split(",");
deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
deque.add(nums[i]);
}
isLeft = true;
if(AC())
makePrintString();
else
sb.append("error").append("\n");
}
System.out.println(sb);
}
public static boolean AC(){
for (char command : p) {
if (command == 'R') {
isLeft = !isLeft;
} else {
if (deque.isEmpty()) {
return false;
}
if (isLeft) {
deque.pollFirst();
} else
deque.pollLast();
}
}
return true;
}
public static void makePrintString(){
sb.append("[");
if (!deque.isEmpty()) {
if (isLeft) {
sb.append(deque.pollFirst());
while(!deque.isEmpty()){
sb.append("," + deque.pollFirst());
}
} else{
sb.append(deque.pollLast());
while(!deque.isEmpty()){
sb.append("," + deque.pollLast());
}
}
}
sb.append("]").append("\n");
}
}