👀 문제 설명
선영이는 주말에 할 일이 없어서 새로운 언어 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를 출력한다.
예제 입력 1
4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]
예제 출력 1
[2,1]
error
[1,2,3,,8]
error
✍🏻풀이
처음에는 단순하게 int 배열을 사용해서 하라는대로 구현했는데, 이렇게 할 경우 시간초과가 발생한다.
-> 테스트케이스는 최대 100이고, 배열의 수는 최대 100,000이기 때문에..
그래서 덱을 사용해서 푸니까 풀렸다!
먼저, [x1,..,xn] 형태로 배열에 들어있는 수를 arrStr에 입력받고, 대괄호를 모두 삭제해준다.
그리고 StringTokenizer을 사용해서 arrStr을 ","를 기준으로 분리시키고, 분리된 숫자들을 덱에 넣어준다.
덱에 숫자를 다 넣었으면, 순서를 저장하는 플래그 first를 사용해 현재 앞에서부터 삭제해야하는지, 뒤에서부터 삭제해야하는지를 표시한다.
그리고, 이 first에 따라 앞에서부터 숫자를 버려야하면, Deque.pollFirst로 삭제하고, 뒤에서부터 버려야하면, Deque.pollLast로 버린다.
이 때, 에러가 발생하면 "error"를 출력하고, 에러가 발생했는지 저장하는 변수 error를 true로 바꿔준다.
함수가 모두 실행되었다면, error 변수를 사용해 에러가 발생하지 않았는지 확인한다.
에러가 발생하지 않았다면, 배열에 든 숫자를 first에 따라 출력해주면 된다. (first가 true면 앞에서부터, false면 뒤에서부터 출력)
* 함수가 모두 실행되고, 에러가 발생하지 않았을 경우 + 배열에 숫자가 없을 때는 []를 출력해줘야 한다!
-> 처음에는 이걸 처리 안해서 틀렸다..!
코드
package boj;
// AC (https://www.acmicpc.net/problem/5430 )
import java.util.*;
import java.io.*;
public class BOJ_5430 {
private static int T;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// input
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
String p = br.readLine(); // 수행할 함수
int n = Integer.parseInt(br.readLine()); // 배열에 들어있는 수의 개수
// [x1, ..., xn] 형태로 배열에 들어있는 수를 입력받고,
// 대괄호를 없앤다.
String arrStr = br.readLine();
arrStr = arrStr.replace("[", "");
arrStr = arrStr.replace("]", "");
// StringTokenizer로 ,를 기준으로 분리시켜준다.
st = new StringTokenizer(arrStr, ",");
// 덱을 사용해서 배열을 표현해준다.
Deque<Integer> arr = new LinkedList<>(); // 함수를 수행하기 위해 덱 사용
for (int i = 0; i < n; i++) {
arr.push(Integer.parseInt(st.nextToken()));
}
// solve
boolean error = false; // 에러가 났는지 확인해주기 위한 플래그
boolean first = false; // 순서를 저장하는 플래그 (앞에서부턴지 뒤에서부턴지)
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == 'R') { // R 이면 순서를 바꾼다.
first = !first;
}
else if (p.charAt(i) == 'D') { // D 이면 덱에서 숫자를 버린다.
// 배열이 비어있는데 D를 사용한 경우 에러 발생
if (arr.size() == 0) {
error = true;
bw.write("error\n");
break;
}
// 에러 발생하지 않았을 경우
if (first) arr.pollFirst(); // 앞에서 숫자 버림
else arr.pollLast(); // 뒤에서 숫자 버림
}
}
// 에러가 발생하지 않고, 모든 함수가 수행되었을 경우
if (!error) {
// 에러가 발생하지 않고, 모든 함수가 수행된 후, 배열이 비어있을 때는 []를 출력해줘야 한다.
if (arr.size() == 0) {
bw.write("[]\n");
}
// 에러가 발생하지 않고, 배열에 숫자가 아직 있으면 배열 출력
else {
if (first) {
bw.write("[");
while (!arr.isEmpty()) {
if (arr.size() == 1) bw.write(arr.pollFirst() + "]\n");
else bw.write(arr.pollFirst() + ",");
}
}
else {
bw.write("[");
while (!arr.isEmpty()) {
if (arr.size() == 1) bw.write(arr.pollLast() + "]\n");
else bw.write(arr.pollLast() + ",");
}
}
}
}
}
bw.flush();
bw.close();
}
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Baekjoon] 동전 2 (0) | 2021.09.26 |
---|---|
[Baekjoon] 게리맨더링 2 (0) | 2021.09.25 |
[JUNGOL] 해밀턴 순환회로 (0) | 2021.09.23 |
[Baekjoon] 게리맨더링 (0) | 2021.09.13 |
[Baekjoon] 이차원 배열과 연산 (0) | 2021.08.26 |