[백준 5430]https://www.acmicpc.net/problem/5430
문제 조건
두 가지 함수 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만을 넘지 않는다.
문제 풀기 전 설계
실제로 배열을 뒤집는 연산은 시간이 매우 오래 걸리고, 삭제가 배열의 가장 앞부분(뒤집혀 있다면 가장 뒷부분)에서만 일어나므로 양방향 Queue의 형태인 Deque 자료구조를 사용하는 것이 좋아 보인다. 배열이 뒤집혔는지 아닌지를 저장하고, 그에 따라 맨 앞이나 맨 뒤의 자료부터 버리면 배열을 뒤집은 것과 같은 기능을 한다.
문제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine()); // 테스트케이스의 개수
fo : for (int i = 0; i < t; i++) { // 중간에 error가 나면 해당 반복문을 continue 하기 위해 라벨 지정
String cmd = br.readLine(); // 수행할 함수
int numOfValue = Integer.parseInt(br.readLine()); // 배열에 들어있는 변수의 초기 개수
st = new StringTokenizer(br.readLine(), "[],"); // 구획문자에 여러개를 넣을 수도 있었다.
Deque<String> dq = new LinkedList<>(); // 배열 값 저장할 Deque
for (int j = 0; j < numOfValue; j++) { // Deque에 StringTokenizer로 토큰화 한 값을 넣어줌
dq.addLast(st.nextToken());
}
boolean isReversed = false; // 배열의 방향을 저장할 boolean형 변수
for (int j = 0; j < cmd.length(); j++) {
if (cmd.charAt(j) == 'R') { // 수행할 함수가 'R'이라면
isReversed = !isReversed; // 배열 방향 반대로
}
else { // 수행할 함수가 'D'이라면
if (dq.isEmpty()) { // Deque가 비어 있다면 "error" 출력
sb.append("error").append('\n');
continue fo; // 해당 반복문 continue
}
else { // Deque에 값이 있다면 방향을 보고 처음 값을 버림
if (isReversed) dq.pollLast();
else dq.pollFirst();
}
}
}
StringBuilder sb2 = new StringBuilder(); // 배열 내부 변수 저장할 StringBuilder
if (isReversed) { // 뒤집힌 방향이면 뒤에서부터 출력
while (!dq.isEmpty()) {
sb2.append(dq.pollLast()).append(',');
}
}
else { // 원래 방향이면 앞에서부터 출력
while (!dq.isEmpty()) {
sb2.append(dq.pollFirst()).append(',');
}
}
if (sb2.length() != 0) sb2.deleteCharAt(sb2.length()-1); // 배열에 변수가 있으면 마지막 ',' 제거
sb.append('[').append(sb2).append(']').append('\n');
}
System.out.println(sb);
}
}문제 풀이
이번 문제는 크게 두 부분을 신경써야 한다. 하나는 입력으로 들어오는 문자열의 파싱이고, 또 다른 하나는 함수의 구현이다.
문자열 파싱은 StringTokenizer의 delimiter(구획문자)를 이용해서 실제로 저장되는 값이 아닌 다른 값을 분리한 후 Deque에 저장했다.
값을 저장하고 나서 실행할 함수를 입력받은 후 문자열의 앞에서부터 해당 문자에 맞는 함수를 실행했다.
함수에서 주의해야 할 부분은 배열이 비어 있다고 무조건 에러가 나는 것이 아니라는 점이다.
에러가 발생하는 상황은 배열이 비어 있고, 'D' 문자가 입력되어 삭제 연산을 할 때이다.
그 점을 주의하고 배열의 삭제나 출력은 배열의 방향을 저장하는 boolean형 변수의 값에 따라 앞에서부터 또는 뒤에서부터 실행하면 된다.
Review
문제의 풀이 자체는 어려운 개념을 사용하지 않았지만, 문제 풀이에 있어 Deque 자료구조를 처음 사용해 본 문제이다. 또 StringTokenizer를 많이 써봤음에도 delimiter를 사용한 경험은 별로 없어서 delimiter에 여러 값을 한 번에 줄 수 있다는 걸 알게 되어 좋았다. 문제에서 요구하는 기능을 구현할 때 여러 자료구조나 알고리즘을 알고 있다면 훨씬 시간적으로나 공간적으로나 효율적이게 된다. 공부 열심히 하자
