성능 요약
메모리: 94056 KB, 시간: 908 ms
분류
덱, 파싱, 구현, 문자열, 자료 구조
제출 일자
2024년 5월 21일 16:14:50
문제 설명
선영이는 주말에 할 일이 없어서 새로운 언어 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를 출력한다.
문제 풀이 (덱 사용)
Deque를 사용하면 그래도 간단하게 풀 수 있는 문제이다.
[자바 - Deque] 덱에 대해 까먹었다면 참고하자.
이 문제는 R,D 명령어를 수행해야 하는 문제인데, 여기서 R (뒤집기)를 할 경우가 문제가 된다.
만약 일일히 하나하나 다 뒤집는다면 테스트 케이스 100개에 명령어 길이는 100000까지, 배열에 들어있는 수의 개수는 100000까지니까...
100 X 100000 X 100000 -> 벌써 제한 시간인 1초를 넘길 거 같은 느낌이다.
그래서 이 문제는 일일히 뒤집으면서 해결해서는 안된다!
그렇기에 Deque를 사용해 앞 뒤에서 값을 뺄 수 있도록 해야 시간초과가 안나온다.
-> boolean형 변수로 reverseCheck를 만들어 뒤집힌 경우와 안뒤집힌 경우로 나눠서 해결했다.
- 만약 뒤집혔다면 값을 맨 마지막에서 빼기
- 뒤집히지 않았다면 처음에서 값 빼기
이렇게 두 가지 경우로 나눠서 해결했다.
그리고 문제가 하나 더 있는데, 문제 설명에서는
D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
라고 작성되어 있지만 만약 배열이 비어있는데 R(뒤집기)만 나온다면?
이라는 생각을 하지 못해 틀렸었다...
[백준 질문게시판 - 16% 오답]을 참고해서 아하! 하고 빈 배열로 출력해야 함을 알아냈다.
만약 본인이 16%에서 계속 틀린다면 한번 이것때문이 아닌 지 체크해보자..!
그래서 errorCheck라는 boolean형 변수를 하나 더 만들고 에러인 경우인지 아닌 지 나눠 조건을 더 만들어서 해결했다.
+ StringTokenizer은 문자열을 나눌 때 한꺼번에 구분할 문자들을 적는 방식이다.
예)st = new StringTokenizer(br.readLine(),"[],"); //구분할 문자들 처리 '[' 그리고 ']' 그리고 ',' 제외기억해두면 나중에 요긴하게 쓰일 것 같아 체크해둔다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
//Deque를 사용해서 해결하는 문제
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Deque<Integer> deque; //Deque 선언
StringTokenizer st; //문자열 입력 받아 원하는 값만 도출하기 위해서
StringBuilder sb= new StringBuilder(); //출력용
int T = Integer.parseInt(br.readLine()); //테스트 케이스 개수 입력받기
String command; //실행할 함수 P
int n; //배열 수
boolean reverseCheck; //뒤집힌 문자열인지 아닌지 체크
boolean errorCheck; //error가 나와야 하는 상황인지 아닌지 체크
for(int i=0; i< T; i++) {
errorCheck=false;
reverseCheck=false; //처음엔 뒤집히지 않음
deque = new ArrayDeque<>(); //deque 생성
command = br.readLine(); //함수 p 입력받기
n=Integer.parseInt(br.readLine()); //배열 수 입력받기
st = new StringTokenizer(br.readLine(),"[],");//구분할 문자들 처리 '[' 그리고 ']' 그리고 ',' 제외
for(int j=0; j<n; j++) {
deque.add(Integer.parseInt(st.nextToken())); //deque에 입력시키기
}
for(int j=0; j<command.length(); j++) {
if(command.charAt(j)=='R') { //R일 경우
if(reverseCheck==false) { //뒤집히지 않았다면?
reverseCheck=true; //뒤집힘
}
else { //뒤집혔다면 ?
reverseCheck=false; //뒤집지 않음
}
}
else if(command.charAt(j)=='D'){ //D일 경우
if(deque.size()==0) { //deque에 아무것도 없다면
errorCheck=true; //에러가 나와야 함
sb.append("error\n");
break;
}
if(!reverseCheck) { //뒤집히지 않았다면
deque.removeFirst(); //첫번째 값 제거
}
else { //뒤집혔다면
deque.removeLast(); //마지막 값 제거
}
}
}
//출력하기
if(!errorCheck) { //에러가 아니라면
//뒤집혔는지 아닌지에 따라 출력 방식 다름
if(!reverseCheck && deque.size()!=0) { //뒤집히지 않았다면
//첫번째 값부터 순서대로 출력하기
sb.append("[");
sb.append(deque.getFirst());
deque.removeFirst();
while(deque.size()!=0) {
sb.append(",");
sb.append(deque.getFirst());
deque.removeFirst();
}
sb.append("]\n");
}
else if(reverseCheck && deque.size()!=0){//뒤집혔다면
//마지막 값에서부터 처음 값으로 역순으로 출력하기
sb.append("[");
sb.append(deque.getLast());
deque.removeLast();
while(deque.size()!=0) {
sb.append(",");
sb.append(deque.getLast());
deque.removeLast();
}
sb.append("]\n");
}
else { //만약 size는 0인데 에러는 아닌 상황이면
sb.append("[]\n");
}
}
}
System.out.println(sb.toString()); //최종 출력
}
}조금 더럽게 푼 느낌이다.
