[백준/boj] 5430: AC (Java) / Deque / 자료구조

문제

5430번: AC

풀이

import java.io.*;
import java.util.*;

public class Main {
	static Deque<Integer> deque;
	static char[] func;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		// 테스트 케이스 만큼 반복
		for (int t = 0; t < T; t++) {
        	// 초기화 및 입력받기
			deque = new ArrayDeque<>();
			func = br.readLine().toCharArray();
			int L = Integer.parseInt(br.readLine());
			// 1
            st = new StringTokenizer(br.readLine(),",");
           
			for (int i = 0; i < L; i++) {
				if(i != 0 && i != L-1) {
					deque.add(Integer.parseInt(st.nextToken()));
					continue;
				}
				char[] temp = st.nextToken().toCharArray();
				String str = "";
				for(int s=0; s< temp.length; s++) {
					if(temp[s] != '[' && temp[s] != ']') {
						str += temp[s];
					}
				}
				deque.add(Integer.parseInt(str));
			}
			
         	// 2 startfunc
			int pointer = startfunc();
			// 3
			if (pointer == 2){ // error
				bw.append("error");
			} else if(pointer == 0) { // 왼쪽 
				bw.append("[");
				while(!deque.isEmpty()) {
					bw.append(deque.poll()+"");
					if(deque.size() != 0)
						bw.append(",");
				}
				bw.append("]");
			} else if (pointer == 1){ // 오른쪽
				bw.append("[");
				while(!deque.isEmpty()) {
					bw.append(deque.pollLast()+"");
					if(deque.size() != 0)
						bw.append(",");
				}
				bw.append("]");
			}
			if(t != T-1)
				bw.append("\n");
		}
		bw.flush();
		bw.close();

	}

	private static int startfunc() { // pointer 반환 , 2: error
		int pointer = 0; // 0: 왼쪽, 1 : 오른
		for (int i = 0; i < func.length; i++) {
			if (func[i] == 'R') {
				pointer = pointer == 0 ? 1 : 0;
			} else { // 'D'
				if (deque.isEmpty())
					return 2;
				if (pointer == 0)
					deque.pollFirst();
				else
					deque.pollLast();
			}
		}
		return pointer;
	}
}

1

• , 를 기준으로 문자열을 나눕니다.
• 첫번째 or 마지막 문자열이 아니라면 바로 deque에 담습니다.
• 첫번째 문자열과 마지막 문자열은 '[' 또는 ']'를 제외한 숫자를 deque에 담습니다.

2 startfunc 함수

• 입력받아온 함수를 수행합니다.
• R함수를 그대로 실행하면 시간, 공간 초과 우려가 있습니다.
  deque는 양방향 큐의 성질을 갖고 있어 함수 수행 후 offer하는 순서에 따라 숫자를 뒤집을 수 있습니다.
  때문에 실제로 Reverse하지 않고, pointer를 통해 앞 뒤 방향만 바꾸는 방법을 생각했습니다.
  • pointer가 0 : 왼쪽이 앞
    pointer가 1 : 오른쪽이 앞
  • return 값
    • 0: 왼쪽이 앞
    • 1: 오른쪽이 앞
    • 2: error (deque가 빈 상태에서 D) 
• D함수는 pointer의 방향에서 offer합니다.
  • 만약 비어있다면 error입니다. (2 반환) 
  • pointer가 0: 맨 왼쪽 숫자 offer(offerFirst)
  • pointer가 1: 맨 오른쪽 숫자 offer(offerLast)
• pointer값을 반환합니다.

3

startfunc 반환 값에 따라 deque 출력 방향을 바꿉니다.

• 0: 왼쪽부터 출력 (offerFirst)
• 1: 오른쪽부터 출력 (offerLast)
• 2: error 출력

 

고려해야할 점

1. 숫자가 1~100까지 이기 때문에 한자리만 deque에 넣으면 안된다.

2. R일때마다 숫자를 reverse하면 시간복잡도가 커지게 된다.

3. 비어있는 괄호가 주어져있을 때 R이면 error가 아니고([]출력), D일때만 error이다.