백준 5430번
https://www.acmicpc.net/problem/5430
문제
생각하기
문제를 이해하고 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());
}
}마지막으로 ']'을 붙여주고 줄바꿈을 넣어주면 끝입니다.
결과
코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static final String ERROR = "error";
private static String P;
private static int N;
private static ArrayDeque<Integer> que;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
input();
bw.write(solve());
}
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
int len = P.length();
boolean flag = true; // 포인터 앞
for (int i = 0; i < len; i++) {
char ch = P.charAt(i);
if (ch == 'R') {
flag = !flag;
} else if (ch == 'D') {
if (que.isEmpty()) {
sb.append(ERROR).append('\n');
return sb.toString();
}
if (flag) {
que.pollFirst();
} else {
que.pollLast();
}
}
}
sb.append('[');
if (flag) {
for (int num : que) {
sb.append(num).append(',');
}
} else {
while (!que.isEmpty()) {
sb.append(que.pollLast()).append(',');
}
}
if (sb.charAt(sb.length() - 1) == ',') {
sb.delete(sb.length() - 1, sb.length());
}
sb.append(']').append('\n');
return sb.toString();
} // End of solve()
private static void input() throws IOException {
P = br.readLine();
N = Integer.parseInt(br.readLine());
String temp = br.readLine();
que = new ArrayDeque<>();
StringTokenizer st = new StringTokenizer(temp.substring(1, temp.length() - 1), ",");
for (int i = 0; i < N; i++) {
que.offer(Integer.parseInt(st.nextToken()));
}
} // End of input()
} // End of Main class
