백준 5430번
https://www.acmicpc.net/problem/5430
문제
선영이는 주말에 할 일이 없어서 새로운 언어 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 ≤ x i ≤ 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생각하기
문제를 이해하고 Deque을 사용해야 된다는 것을 곧바로 파악해야하는 문제입니다.
처음에 저는 덱을 생각하지 못하고 Array로 구현을 하려고 엄청난 삽질을 했는데, 시간초과 때문에 결국 다른분들의 풀이를 참고할 수 밖에 없었습니다.
시간초과가 나는 이유는 간단합니다. 앞과 뒤를 번갈아가면서 지우고를 반복하면
위치를 계속 바꾸고 배열의 위치를 앞으로 당기는 등의 동작을 반복해야되는데,
최대 100개의 테스트케이스가 모두 10만의 숫자로 구성되어있다고 생각하면,
배열을 역으로 만드는 것만 해도 10만번의 동작이 필요합니다. 엄청난 자원의 낭비가 됩니다.
이 문제에서 파악해야 할 점
여기서 파악할 점은 곧 제가 놓쳤서 틀렸던 부분들입니다.
-
처음에는 Deque이 비었을 경우 무조건 "error"를 출력했는데, 생각해보면 정상적인 방법으로도 Deque이 비어있을 수도 있기 때문에 Deque이 비었을 때는 "[]" 를 출력해줘야 합니다.
-
배열이 비어있는 상태에서 R은 "error"가 발생하지 않습니다.
-
배열에 들어갈 수 있는 숫자는 최대 100이기 때문에 charAt()을 사용해서 끊으면 안됩니다.
동작
먼저 배열형식으로 들어오는 테스트케이스를 [,]를 기준으로 토큰처리해서 숫자로 만들어서 deque에 넣어줍니다. 함수는 p로 저장해둡니다.
StringTokenizer st = new StringTokenizer(br.readLine(),"[],");
deque = new ArrayDeque<Integer>();
for(int i=0; i<number; i++) {
deque.add(Integer.parseInt(st.nextToken()));
}이제 AC함수를 실행합니다. p로 들어온 값으로 함수를 실행합니다.
forward_direction 는 현재 배열의 순서가 정방향인지 역방향인지 나타냅니다.
기본값은 정방향이기때문에 true로 초기화해주었습니다.
p의 값을 char형태로 하나씩 분리해서 R과 D를 구분합니다.
R일 경우 forward_direction를 역으로 바꿔줍니다.
if(function == 'R') {
forward_direction = !forward_direction;
continue;
}이후에는 forward_direction의 값 즉, 방향에 따라 조건을 걸어줍니다.
정방향일 때, pollFirst와 했는데 null을 반환할 경우 비었는데 D를 사용한 것이므로 "error"를 곧바로 return 해줍니다.
역방향일 때, pollLast와 했는데 null을 반환할 경우 비었는데 D를 사용한 것이므로 "error"를 곧바로 return 해줍니다.
// 정방향일 때
if( forward_direction ) {
// 덱이 비었으면,
if(deque.pollFirst() == null) {
sb.append("error\n");
return;
}
}
// 역방향 일때 forward_direction = true
else {
if(deque.pollLast() == null) {
sb.append("error\n");
return;
}
}이후에 출력은 makePrintString 메소드가 담당합니다.
"error" 가 나오지 않았을 경우 이 곳으로 넘어옵니다. "error"의 경우 return으로 빠져나갔기 때문에 이곳으로 오지 못합니다.
가장 먼저 '['가 sb에 추가 됩니다.
그리고 forward_direction이 true일때는 정방향이므로 가장 먼저 한 줄을 출력하고 난 뒤
','가 붙을지 안붙을지 판단하기 위해서 deque.isEmpty()를 판별합니다
만약 deque이 비어있지 않다면, ','를 사이에 두고 앞에서 부터 계속 원소를 꺼냅니다.
역방향도 deque.pollLast()만 다르고 과정은 같습니다.
if(forward_direction) {
sb.append(deque.pollFirst());
while(!deque.isEmpty()) {
sb.append(',').append(deque.pollFirst());
}
}
else {
sb.append(deque.pollLast());
while(!deque.isEmpty()) {
sb.append(',').append(deque.pollLast());
}
}마지막으로 ']'을 붙여주고 줄바꿈을 넣어주면 끝입니다.
TMI
풀다가 ㄹㅇ AC육성으로 나옴..
코드
import java.io.*; import java.util.*; public class Main { static ArrayDeque<Integer> deque; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); while(T --> 0) { String p = br.readLine(); int number = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine(),"[],"); deque = new ArrayDeque<Integer>(); for(int i=0; i<number; i++) { deque.add(Integer.parseInt(st.nextToken())); } AC(p); } System.out.println(sb); } // End of main static void AC(String p) { boolean forward_direction = true; for(char function : p.toCharArray()) { if(function == 'R') { forward_direction = !forward_direction; continue; } // 정방향일 때 if( forward_direction ) { // 덱이 비었으면, if(deque.pollFirst() == null) { sb.append("error\n"); return; } } // 역방향 일때 forward_direction = true else { if(deque.pollLast() == null) { sb.append("error\n"); return; } } } makePrintString(forward_direction); } private static void makePrintString(boolean forward_direction) { sb.append('['); if(deque.size() > 0) { if(forward_direction) { sb.append(deque.pollFirst()); while(!deque.isEmpty()) { sb.append(',').append(deque.pollFirst()); } } else { sb.append(deque.pollLast()); while(!deque.isEmpty()) { sb.append(',').append(deque.pollLast()); } } } sb.append(']').append('\n'); } // End of makePrintString } // End of class
