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

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

풀이

import java.io.*; import java.util.*; public class Main { static Deque 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("

"); } 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)

deque는 양방향 큐의 성질을 갖고 있어 함수 수행 후 offer하는 순서에 따라 숫자를 뒤집을 수 있습니다. 때문에 실제로 Reverse하지 않고, pointer를 통해 앞 뒤 방향만 바꾸는 방법을 생각했습니다. 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이다.

from http://sohee-dev.tistory.com/137 by ccl(A) rewrite - 2021-09-25 18:27:10