[문제]
선영이는 주말에 할 일이 없어서 새로운 언어 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를 출력한다.
[예제 입력]
4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[][예제 출력]
[2,1]
error
[1,2,3,5,8]
error
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스 개수
for (int i = 0; i < T; i++) {
Deque<Integer> dq = new ArrayDeque<>();
String func = sc.next(); // 수행할 함수
int n = sc.nextInt(); // 배열에 들어있는 수의 개수
String x = sc.next(); // 배열에 들어있는 정수
String xArr = x.substring(1, x.length() - 1); // [] 제거
// , 기준으로 분리해 deque에 넣기
StringTokenizer st = new StringTokenizer(xArr, ",");
for (int j = 0; j < n; j++) {
dq.offer(Integer.parseInt(st.nextToken()));
}
AC(dq, func); // 수행할 함수와 덱 넘겨주기
}
}
private static void AC(Deque<Integer> dq, String func) {
boolean flag = true; // 방향 나타내는 변수
// 함수 분리
for (int i = 0; i < func.length(); i++) {
char p = func.charAt(i);
int num = 0;
if (p == 'R') {
flag = !flag; // 방향 변경
if (!dq.isEmpty()) {
if (flag) { // 정방향
num = dq.peekFirst();
}
else if (!flag) { // 역방향
num = dq.peekFirst();
}
}
}
else if (p == 'D') {
// 비어있는 경우 error 출력
if (dq.isEmpty()) {
System.out.println("error");
return;
}
else {
if (flag) { // 정방향
dq.removeFirst();
}
else if (!flag) { // 역방향
dq.removeLast();
}
}
}
}
StringBuilder sb = new StringBuilder();
if (dq.isEmpty()) {
System.out.println("[]");
}
else {
if (flag) {
int size = dq.size();
sb.append("[");
for (int i = 0; i < size - 1; i++) {
sb.append(dq.pollFirst() + ",");
}
sb.append(dq.pollFirst() + "]");
System.out.println(sb);
}
else if (!flag) {
int size = dq.size();
sb.append("[");
for (int i = 0; i < size - 1; i++) {
sb.append(dq.pollLast() + ",");
}
sb.append(dq.pollLast() + "]");
System.out.println(sb);
}
}
}
}
'R' 연산의 경우를 어떻게 처리해야 할 지 고민하다가,
덱을 하나 더 만들어서 기존 덱에서 뒤에서부터 하나씩 빼서 넣어주는 방식으로 코드를 작성했는데
시간초과가 떴다.
아무래도 R 연산 때문에 시간 초과가 나는 것 같아 이 방법 저 방법 시도를 하다가 검색을 했는데,
굳이 다시 역순으로 해주지 않아도 되는 방법이 있단 걸 알게됐다!
정방향/역방향을 나타내는 boolean 변수를 하나 두고 (true=정방향, false=역방향)
그에 따라 'D' 연산과 출력을 해주면 되는 것이었다.
자세히 풀어서 설명을 하자면,
'D' 연산의 경우도 어차피 첫 번째 수만 버리기 때문에 boolean 변수의 값에 따라
값을 빼두면 된다.
=> 정방향의 경우 덱에서 첫번째 수를, 역방향의 경우 덱에서 마지막 수를!
출력도 마찬가지로
boolean 변수 값에 따라 출력을 시작하는 방향만 다르게 하면 해결된다.
또 까다로웠던 점은,
'R' 연산의 경우 'D' 연산과 다르게 비어있어도 에러를 출력하지 않는다는 점과
마지막에 덱에 남아있는 수를 출력할 때 비어있는 경우도 [] 를 출력해줘야 한다는 점이었다.
그래서 나는 연산을 처리해주는 AC 함수를 따로 만들고,
덱이 비어있는데 'D' 연산을 한 경우엔 error를 출력하고 바로 return을 시키고,
그렇지 않은 경우('R' 연산을 했거나, 비어있지 않은데 'D' 연산을 한 경우)엔 StringBuilder에 덱에 있는 값들을 넣어주었다.
또한 'R' 연산을 했는데, 덱이 비어있는 경우도 처리해줘야 했기 때문에
덱이 비어있지 않은 경우만 peekFirst, peekLast를 하도록 했고,
모든 연산이 끝났는데 덱이 비어있는 경우엔 [] 를 출력할 수 있도록 AC 함수 끝에서 처리해줬다.
+) 추가로, StringTokenizer로 [], 를 모두 제외할 수 있는지 모르고
위의 코드에서는 substring으로 [] 를 제거하고 그 후에 또 StringTokenizer로 콤마(,) 를 구분해줬는데
[], 를 모두 제외할 수 있어서 바꿔서 코드를 작성했다 (아래 코드)
StringTokenizer 관련 포스팅 : https://gr616.tistory.com/326
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 테스트 케이스 개수
for (int i = 0; i < T; i++) {
Deque<Integer> dq = new ArrayDeque<>();
String func = sc.next(); // 수행할 함수
int n = sc.nextInt(); // 배열에 들어있는 수의 개수
String x = sc.next(); // 배열에 들어있는 정수
// 분리해 숫자만 deque에 넣기
StringTokenizer st = new StringTokenizer(x, "[],");
for (int j = 0; j < n; j++) {
dq.offer(Integer.parseInt(st.nextToken()));
}
AC(dq, func); // 수행할 함수와 덱 넘겨주기
}
}
private static void AC(Deque<Integer> dq, String func) {
boolean flag = true; // 방향 나타내는 변수
// 함수 분리
for (int i = 0; i < func.length(); i++) {
char p = func.charAt(i);
int num = 0;
if (p == 'R') {
flag = !flag; // 방향 변경
if (!dq.isEmpty()) {
if (flag) { // 정방향
num = dq.peekFirst();
}
else if (!flag) { // 역방향
num = dq.peekFirst();
}
}
}
else if (p == 'D') {
// 비어있는 경우 error 출력
if (dq.isEmpty()) {
System.out.println("error");
return;
}
else {
if (flag) { // 정방향
dq.removeFirst();
}
else if (!flag) { // 역방향
dq.removeLast();
}
}
}
}
StringBuilder sb = new StringBuilder();
if (dq.isEmpty()) {
System.out.println("[]");
}
else {
if (flag) {
int size = dq.size();
sb.append("[");
for (int i = 0; i < size - 1; i++) {
sb.append(dq.pollFirst() + ",");
}
sb.append(dq.pollFirst() + "]");
System.out.println(sb);
}
else if (!flag) {
int size = dq.size();
sb.append("[");
for (int i = 0; i < size - 1; i++) {
sb.append(dq.pollLast() + ",");
}
sb.append(dq.pollLast() + "]");
System.out.println(sb);
}
}
}
}
전체적으로 어려운 난이도의 문제는 아니라고 생각했지만,
막상 코드를 작성해보면 까다로운 조건들이 있어서 코드가 많이 길어진 듯 싶다.
문자열 분리와 추가하는 부분이 좀 까다롭고, 'R' 연산을 처리하는 것이 포인트인 문제였다!
'Algorithm > Baekjoon' 카테고리의 다른 글
| 백준 / 2712번 / 미국 스타일 (0) | 2023.01.06 |
|---|---|
| 백준 / 1931번 / 회의실 배정 (0) | 2023.01.06 |
| 백준 / 17626번 / Four Squares (dp) (0) | 2023.01.04 |
| 백준 / 10026번 / 적록색약 (0) | 2023.01.03 |
| 백준 / 1389번 / 케빈 베이컨의 6단계 법칙 (Floyd 알고리즘) (0) | 2023.01.02 |