[백준] 5430번 AC (Deque_JAVA)

시간과의 싸움인 문제다!

 

시간을 줄이기 위한 자료구조가

무엇이 있을까 계속 생각해야 하는 문제고,

새로운 것을 또 배운 문제이기도 하다.

 

---

문제

 

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

5430번: AC

 

 

---

설계

 

알고리즘 설계 [접근 방법] : Deque

숫자배열을 입력받고, 명령어가 'R'이면 배열을 뒤집어야한다.

하지만 배열을 직접 뒤집는 것보다, 삽입과 호출이 앞, 뒤 모두 가능한 Deque가 시간이 훨씬 빠르기에 Deque를 사용했다.

isfirst 변수를 두어, 이 변수가 true이면 현재 상황은 앞->뒤이고, false라면 뒤->앞이 되는 것이다.

 

풀이 과정

1.

명령어를 문자 배열로 입력받는다.

 

2.

정수배열을 입력받아야하는데, 입력어가 배열 모양이므로 문자로 입력받은다.

그 후 문자 '[', ']'를 subString을 사용해 자른다. 또한, ',' 기호도 split을 사용해 문자열을 자른다.

 

3.

Deque를 생성한 후 자른 문자열 배열을 넣어준다.

이때 조심해야할 것은 문자열 배열이 빈 배열일 수 있으므로, 배열이 비었지 않았을 경우에만 Deque에 넣어야 한다.

이때 isfirst는 true로 설정한다.

 

4.

이제 반복문을 돌며 명령어를 실행한다.

명령어가 'R'이라면 isfirst를 반전시킨다.

명령어가 'D'라면 Deque의 크기를 확인하여, Deque안에 문자가 있다면 방향을 확인하여 삭제한다.

그리고 명령어가 'D'이며, Deque의 크기가 0이라면 flag를 flase로 변환시킨 뒤 반복문을 종료한다.

 

5.

현재까지 Deque에 있는 값들을 StringBuilder에 넣어준다.

이 때, isfirst가 true라면 앞에서부터 StringBuilder에 넣고, false라면 뒤에서부터 넣어야한다.

 

그리고 flag가 true라면 StringBuilder를 출력하고, flase라면 error를 출력한다.

 

 

---

코드

 

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

public class Test_5430_AC {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int test = Integer.parseInt(br.readLine());
		
		for(int t=0; t<test; t++) {
			
			//명령어 문자 배열로 변경하기
			char[] charArr = br.readLine().toCharArray();
			
			int n = Integer.parseInt(br.readLine());
			
			//정수 배열 입력받기
			String str = br.readLine();
			str = str.substring(1, str.length()-1);
			String[] numArr = str.split(",");
			
			
			//Dequeue사용
			Deque<String> deque = new ArrayDeque<>();
			for(int i=0; i<numArr.length; i++) {
				if(!numArr[i].equals("")) deque.add(numArr[i]);
			}
			
			boolean isfirst = true;
			boolean flag = true;
			
			for(int i=0; i<charArr.length; i++) {
				
				//R > 반전하기
				if(charArr[i]=='R') {
					isfirst = !isfirst;
				}
				
				//D > 삭제하기
				else if(charArr[i]=='D' && deque.size()!=0) {
					if(isfirst) deque.poll();
					else deque.pollLast();
				}
				
				//D > error
				else if(charArr[i]=='D' && deque.size()==0) {
					flag = false;
					break;
				}
			}
			
			
			//StringBuilder 사용
			StringBuilder sb = new StringBuilder();
			while(!deque.isEmpty()) {
				if(isfirst) sb.append(deque.poll());
				else sb.append(deque.pollLast());
				
				if(!deque.isEmpty()) sb.append(",");
			}
			
			//출력
			if(flag) bw.write("[" +sb.toString()+ "]" + "\n");		
			else bw.write("error" + "\n");
		}
		
		bw.flush();
		bw.close();
	}
}

 

 

(❁´◡`❁)

끝!