[백준/java] 5430번: AC - 큐

5430번: AC

https://www.acmicpc.net/problem/5430

5430번: AC

 

5430번: AC 제출 현황

 

제출만 9번한 이 문제..

간단하게 여겼지만 생각보다 그리 간단하지는 않았던 문제였다.

 

반응형

 

★ 1 'R' 연산 시 덱을 통으로 역순 정렬 → 시간 초과 발생

처음에 'R' 연산 시 역순으로 정렬하였다.

Collections.reverse((List<?>)deq);

를 사용하여 덱을 역순으로 정렬하였었다.

그래서 처음에는 while문 안에 deq.isEmpty()를 넣어서 'D' 연산이 아니더라도 덱에 데이터가 없으면 while문을 빠져나와서 에러처리를 했었다.

while(k < cmd.length()) {
	if(deq.isEmpty()) break;
	char ch = cmd.charAt(k);
	switch (ch) {
	case 'R':
		Collections.reverse((List<?>)deq);
		break;
	case 'D':
		deq.poll();
		break;
	}
	k++;
}

if(deq.isEmpty()) {
	bw.write("error\n");
}

 

근데 백준에서 원하는 대답이 아니었던지라 계속 답변이 틀렸다.

일단 'R' 연산을 수행할 때마다 뒤집어주면 수행 시간에 있어서 마이너스요소가 되는 것 같다.

 

★ 'R' 연산에서 Collections.reverse(deq) 대신에 boolean으로 poll 방향을 바꾸어 주면 더 빠르다

boolean dir = true;
boolean errYN = false;

int k = 0;
while(k < cmd.length()) {
	char ch = cmd.charAt(k);
	switch (ch) {
	case 'R':
		dir = !dir;
		break;
	case 'D':
		if(deq.isEmpty()) {
			errYN = true;
		} else {
			if(dir) deq.pollFirst();
			else deq.pollLast();
		}
		break;
	}
	if(errYN) break;
	k++;
}

위의 코드처럼 'R' 연산일때 dir에 !dir 만 넣어주면 매번 R 연산할 때마다 굳이 덱 전체를 뒤집을 필요가 없어진다.

 

728x90

★ Collections.reverse(deq) 을 기반으로 생각하여 덱에 데이터가 없을 때 'R' 연산을 수행한다는거 자체가 말이 안된다고 생각해서 while문 시작 바로 밑 부분에 deq.isEmpty()를 넣어서 비어있으면 바로 while문을 나가게 하고 error가 출력되도록 했었는데 이것 때문에 계속 틀리게 되었다.

 

dir로 방향전환만 해주면 굳이 덱에 데이터 유무를 따질 필요가 없어졌어서 'D'일 때만 덱이 비어있는지를 확인해주면 되는 거였다.

 

그래서 변수 boolean errYN = false; 를 추가해주고 'D' 연산일 때 deq.isEmpty()가 true이면 while문을 빠져나와서 error를 출력하게 해주었다.

 

 

★ 다음은 StringBuilder를 사용하여 출력을 완성한 소스이다.

많은 사람들이 이 방법을 채택하였다.

package queue;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;
public class AC {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			Deque<Integer> deq = new LinkedList<Integer>();
			String cmd = br.readLine();
			int n = Integer.parseInt(br.readLine());
			String[] arr = br.readLine().replace("[", "").replace("]", "").split(",");
			for (int i = 0; i < n; i++) deq.add(Integer.parseInt(arr[i]));
			boolean dir = true;
			boolean errYN = false;
			
			int k = 0;
			while(k < cmd.length()) {
				char ch = cmd.charAt(k);
				switch (ch) {
				case 'R':
					dir = !dir;
					break;
				case 'D':
					if(deq.isEmpty()) {
						errYN = true;
					} else {
						if(dir) deq.pollFirst();
						else deq.pollLast();
					}
					break;
				}
				if(errYN) break;
				k++;
			}
			
			if(errYN) {
				bw.write("error\n");
			} else {
				sb = new StringBuilder();
				bw.write("[");
				while(!deq.isEmpty()) {
					if(dir) sb.append(deq.pollFirst());
					else sb.append(deq.pollLast());
					if(!deq.isEmpty()) sb.append(",");
				}
				bw.write(sb + "]\n");
			}
		}
		
		bw.flush();
	}
}

 

StringBuilder를 사용한 것(위의 소스, 아래의 결과)과 사용하지 않은 것의 차이(아래의 소스, 위의 결과)

★ 다음은 StringBuilder를 사용하지 않고 출력을 완성하는 소스이다.

이렇게 한 소스는 아마 못본거같다. 이 소스도 통과되었으나 확실히 StringBuilder를 쓰는게 더 빠른거같다.

 

package queue;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
public class AC {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			Deque<Integer> deq = new LinkedList<Integer>();
			String cmd = br.readLine();
			int n = Integer.parseInt(br.readLine());
			String[] arr = br.readLine().replace("[", "").replace("]", "").split(",");
			for (int i = 0; i < n; i++) deq.add(Integer.parseInt(arr[i]));
			boolean dir = true;
			boolean errYN = false;
			
			int k = 0;
			while(k < cmd.length()) {
				char ch = cmd.charAt(k);
				switch (ch) {
				case 'R':
					dir = !dir;
					break;
				case 'D':
					if(deq.isEmpty()) {
						errYN = true;
					} else {
						if(dir) deq.pollFirst();
						else deq.pollLast();
					}
					break;
				}
				if(errYN) break;
				k++;
			}
			
			if(errYN) {
				bw.write("error\n");
			} else {
				String str = "";
				
				if(dir) str = deq.toString().replaceAll(" ", "");
				else {
					Collections.reverse((List<?>)deq);
					str = deq.toString().replaceAll(" ", "");
				}
				
				bw.write(str + "\n");
			}
		}
		
		bw.flush();
	}
}