[백준] 5430 AC (Java)

[5430 AC]

난이도: 골드5

5430번: AC

문제

입력

출력

---

[아이디어]

이 문제는 두가지 방법으로 풀어볼 수 있다. R이 나올 때마다 정말 배열을 뒤집으면 시간초과가 난다. 

 

하나는 덱을 사용하는 방법이고, 다른 하나는 투포인터를 사용하는 방법이다.

덱을 사용하는 것은 단순하게 앞에서 삭제할지 뒤에서 삭제할지를 저장하는 변수를 통해 덱의 내장함수인 removeFirst(), removeLast(), pollFirst(), pollLast() 를 사용해주었다.

투포인터를 사용할 때는 st와 end 위치를 저장하는 변수와 삭제 위치를 저장하는 변수를 사용하였다.

 

두 방법의 실행시간은 거의 동일하다. 하지만, 메모리가 꽤 차이난다.

---

[JAVA 코드]

1. 덱 사용

// 메모리: 94020KB
// 실행시간: 764ms

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 {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int T, N, dir;
	static String command;
	static Deque<Integer> nums;

	public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(br.readLine());
		tc: for(int t = 0; t < T; t++) {
			command = br.readLine();
			N = Integer.parseInt(br.readLine());			
			String temp = br.readLine();
			tokens = new StringTokenizer(temp.substring(1, temp.length() - 1), ",");
			nums = new ArrayDeque<>();
			for(int i = 0; i < N; i++) {
				nums.add(Integer.parseInt(tokens.nextToken()));
			}
			
			dir = 1; // 앞에서부터!
			for(int i = 0; i < command.length(); i++) {
				switch(command.charAt(i)) {
				case 'R':
					dir *= -1;
					break;
				case 'D':
					// 비어있는 경우 에러
					if(nums.isEmpty()) {
						output.append("error\n");
						continue tc;
					}
					
					if(dir == 1) { // 앞에서 제거
						nums.removeFirst();
					} else { // 뒤에서 제거
						nums.removeLast();
					}
					break;
				}
			}
			
			output.append("[");
			if(dir == 1) {
				int size = nums.size();
				for(int i = 0; i < size; i++) {
					if(i > 0) output.append(",");
					output.append(nums.pollFirst());
				}
			}
			else {
				int size = nums.size();
				for(int i = 0; i < size; i++) {
					if(i > 0) output.append(",");
					output.append(nums.pollLast());
				}
			}
			output.append("]\n");
		}
		System.out.println(output);
	}
}

 

2. 투포인터 사용

// 메모리: 68120KB
// 실행시간: 760ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int T, N, st, end;
	static boolean order;
	static String command;
	static int [] nums;

	public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(br.readLine());
		tc: for(int t = 0; t < T; t++) {
			command = br.readLine();
			N = Integer.parseInt(br.readLine());			
			tokens = new StringTokenizer(br.readLine(), "[],");
			nums = new int [N];
			for(int i = 0; i < N; i++) {
				nums[i] = Integer.parseInt(tokens.nextToken());
			}
			
			order = true; // 앞에서부터!
			st = 0;
			end = N - 1;
			for(int i = 0; i < command.length(); i++) {
				switch(command.charAt(i)) {
				case 'R':
					if(order) order = false;
					else	  order = true;
					break;
				case 'D':
					// 비어있는 경우 에러
					if(st > end) {
						output.append("error\n");
						continue tc;
					}
					
					if(order) { // 앞에서 제거
						st++;
					} else { // 뒤에서 제거
						end--;
					}
					break;
				}
			}
			
			output.append("[");
			if(order) {
				for(int i = st; i <= end; i++) {
					if(i != st) output.append(",");
					output.append(nums[i]);
				}
			} else {
				for(int i = end; i >= st; i--) {
					if(i != end) output.append(",");
					output.append(nums[i]);
				}
			}
			output.append("]\n");
		}
		System.out.println(output);
	}

}