[백준] 5430번 : AC - JAVA [자바]

 
www.acmicpc.net/problem/5430

5430번: AC

 

 

---

• 문제

 

 

 

 

덱의 원리만 이해한다면 매우 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제는 그렇게 어려운 문제는 아니다.

 

이 번 문제는 덱(Deque) 자료구조를 이용하여 푸는 문제이므로 가능하다면 아래 덱(Deque) 자료구조에 대해 어떻게 구현되고 원리는 무엇인지 이해하고 오시면 좋을 것 같다.

 

배열 덱

자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기

 

 

연결리스트 덱

자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기

 

 

 

 

 

알고리즘 풀이는 덱(Deque) 자료구조를 이해한다는 가정하에 풀이하도록 하겠다.

 

 

 

이 문제의 정답비율이 생각보다 낮은데, 보니 거의 런타임 에러 아니면 시간초과, 틀렸습니다 였다. 아마 크게 세 가지 이유이지 않을까 싶다.

1. 배열을 뒤집는 과정

2. 에러 발생 처리

3. 대괄호를 정규식으로 분리하여 숫자만 얻는 과정

 

 

 

일단, 첫 번째 부터 보자. 배열을 뒤집는 과정이다. 아마 시간초과로 실패했다면 배열을 뒤집었기 때문일 것이고, 만약 뒤집지 않았더라도 D연산, 즉 앞에서 뽑는 연산을 뒤집힌 상태에서의 첫 번째 원소를 잘못 가리키고 있어 틀렸을 가능성이 높다.

 

 

조금만 생각해보면 알겠지만, 굳이 뒤집어 줄 필요가 없다.

 

예로들면 이렇다.

 

 

 

 

 

 

아마 방법 1 처럼 배열을 뒤집는 과정을 직접 구현하면 시간초과가 날 것이다..

 

그러면 어떻게 하냐.

바로 Deque을 활용하여 방법 2처럼 양방향에서 접근 할 수 있는 큐를 활용하는 것이다.

즉, 방향을 가리키는 변수를 두고 true냐 false냐에 따라 front를 어디로 볼 것인지 정하면 된다. 그러면 그 방향에 따라 배열 원소를 마치 뒤집는 것처럼 활용할 수 있다는 것이다.

 

 

쉽게 말해서 Deque에서 삭제 연산은 크게 두 가지가 존재한다.

pollFirst() (또는 removeFirst()) : 맨 앞의 원소(배열로 치면 index 0)를 삭제한다.

pollLast() (또는 removeLast()) : 맨 뒤의 원소(배열로 치면 index (arr.length - 1))를 삭제한다.

 

이 때 isRight가 true라면, front가 가장 왼쪽 원소(index 0)라는 의미이므로 pollFisrt() 을 하면 되고, false라면 front를 맨 뒤 원소로 보고 pollLast()을 하면 된다.

 

 

 

 

 

 

그 다음 에러 처리다.

만약 덱에 원소가 없는데 D 연산을 하면 error을 출력하도록 되어있다.

 

크게 두 가지 방법이 있는데, D 연산을 할 때마다 원소를 삭제하기 전에 삭제할 요소가 있는지 검사하기 위해 Deque의 size를 알아내는 방법이 있고, 일단 삭제를 해놓고, 예외가 발생하거나 특정 값을 던지면 error을 출력하도록 하는 방법이 있다.

 

첫 번째 방법은 if(deque.size() == 0) 이라는 조건만 붙여주면 된다는 것은 쉽게 알 것이다.

 

두 번째 방법에 대해 조금 자세하게 설명하자면 이렇다. 덱(Deque)의 API를 보면 다음과 같은 걸 볼 수 있다.

 

링크 : docs.oracle.com/javase/8/docs/api/java/util/Deque.html

 

 

쉽게 말해서 만약에 삭제할 요소가 없는데 삭제를 하려는 경우 remove 계열(removeFirst(), removeLast()) 을 쓰면 NoSuchElementException 예외를 던지고, poll 계열(pollFirst(), pollLast())을 쓰면 Special value, 즉 null 또는 false를 반환한다. 여기서 poll 계열은 null을 반환한다.

 

물론, remove를 사용하여 try-catch 문으로 예외를 처리해도 되나, 그러면 코드가 복잡해지므로... poll 계열을 쓰도록 하겠다.

즉, 일단 poll()을 해놓고 반환된 원소가 null이라면 error을 출력하도록 하고, 아닐경우 그대로 진행시키면 되는 것이다.

 

 

 

 

마지막으로 입력으로 들어오는 [1,2,3,4] 와 같이 대괄호 및 반점을 처리하는 방법이다.

 

일단, Java에서 문자열을 분리하는 방법은 크게 두 가지가 있는데,

필자는 알고리즘 풀이에선 StringTokenizer을 주로 사용하지만 평소에는 split() 을 사용한다. (물론 split()이 권장방식이다.)

 

우리가 구분해야 할 문자는 크게 여는 대괄호([), 닫는 대괄호(]), 반점(,)이다.

 

StringTokenizer는 정규식 검사가 아니기 때문에 구분하려는 문자들을 하나의 문자열로 인자를 넘겨주면 된다.

아래와 같이 말이다.

 

StringTokenizer st = new StringTokenizer(string, "[],");

 

 

 

다만, split()으로 분할하고자 하는 경우 조금 복잡하다.

 

정규식을 사용할 줄 알면, 보통 두 가지중 하나를 사용 할 것이다.

 

String[] s1 = string.split("[\\[\\]\\,]");
String[] s2 = string.split("[^0-9]");

 

split()의 원리를 이해하면 편하겠지만, 이 것을 얘기하면 길어지니 간단하게 말하자면,

 

현재 위치에서 분할하고자 하는 문자와 매칭된 문자가 존재할 경우 선행 문자열과 분할이 된다.

 

 

이 말은, 우리가 [1,2,3,4] 를 분할하고자 한다면 다음과 같이 된다는 것이다.

 

String[] s1 = "[1,2,3,4]".split("[\\[\\]\\,]");

 

위에서 맨 첫번째 "[" 는 정규식에 의해 분리가 될 것이다.

그러면 [ 을 기준으로 이전 문자열과 분리가 되는데, [ 앞에는 빈 문자열이다. 즉, "[" 문자에 의해 분리가 일어나게 되면 다음과 같이 되는 것이다.

"" + "1,2,3,4]

 

이런식으로 첫 번째 인자부터 정규식에 걸려나올 경우 그 이전의 문자열은 빈 문자열이기 때문에 반환되는 String[] 배열의 첫 번째 원소 또한 빈 문자열 "" 로 나온다.

 

그 뒤부터는 선행 문자열이 모두 존재하기에 잘 분리되어 나온다.

 

 

결과적으로 다음과 같이 나오게 된다.

 

String[] s1 = "[1,2,3,4]".split("[\\[\\]\\,]");

/*
 s1[0] = "";
 s1[1] = "1";
 s1[2] = "2";
 s1[3] = "3";
 s1[4] = "4";
*/

 

이는 여러분이 의도하던 문자열 분리가 아닐 것이다.

 

 

그렇기에 만약 split()을 쓰고자 한다면 subString을 통해 대괄호를 비워준 뒤 반점(,) 만 정규식으로 넘겨주면 된다.

 

String s = "[1,2,3,4]";
String subS = s.subString(1, s.length - 1);	// subS = "1,2,3,4"
String[] s1 = subS.split(",");

/*
 s1[0] = "1";
 s1[1] = "2";
 s1[2] = "3";
 s1[3] = "4";
*/

 

 

 

어떤 방법이 편한지는 여러분의 선택이지만, 필자는 StringTokenizer을 사용하여 분리해주도록 하겠다.

 

 

 

 

 

나머지는 이제 문제에 맞춰 구현하면 되므로 코드와 주석을 보면서 이해하도록 하자.

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

 

 

이 번 문제는 입력을 달리하여 성능을 비교하고자 한다.

또한 이 번 문제는 출력량이 많을 것으로 예상되어 출력의 경우 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.

 

1. Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.ArrayDeque;

public class Main {

	public static Scanner in = new Scanner(System.in);
	public static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {

		
		ArrayDeque<Integer> deque;
		StringTokenizer st;
		
		int T = in.nextInt();
		
		
		
		while(T --> 0) {
			
			String command = in.next();	// 문제에서 p에 해당하는 명령어
			int n = in.nextInt();
			
			/*
			 *  [a,b,c,...,x] 중 구분해야 할 것은 대괄호([, ])와 반점(,) 이다.
			 *  StringTokenizer로 여러 구분자를 사용 하고 싶다면
			 *  구분할 문자들을 합쳐서 넘겨주면 된다.
			 *  
			 *  만약 split()을 사용하고싶은 경우 정규식으로는
			 *  String input = br.readLine();
			 *  String[] s = input.subString(1, input.length - 1).split(","); 을 해주어야 한다.
			 *  
			 *  subString을 쓰지않고, split("[^0-9]") 또는, 
			 *  split("[\\[\\]\\,") 같이 정규식으로만 쓴다면 첫 번째 인자가 정규식에 걸려
			 *  빈 문자열을 반환하게 되기 때문
			 *  
			 *  ex)
			 *  str = "[1,2,3,4]";
			 *  strr[] = str.split("[\\[\\]\\,");
			 *  
			 *  result)
			 *  strr[0] = ""
			 *  strr[1] = "1"
			 *  strr[2] = "2"
			 *  strr[3] = "3"
			 *  strr[4] = "4"
			 */
			st = new StringTokenizer(in.next(), "[],");
			
			deque = new ArrayDeque<Integer>();
			
			// 덱에 배열 원소를 넣어준다.
			for(int i = 0; i < n; i++) {
				deque.add(Integer.parseInt(st.nextToken()));
			}
			
			AC(command, deque);
		}
		
		System.out.println(sb);
		
	}
	
	public static void AC(String command, ArrayDeque<Integer> deque) {
		
		boolean isRight = true;	// 방향 상태 변수
		
		for(char cmd : command.toCharArray()) {
			
			if(cmd == 'R') {
				isRight = !isRight;	// 방향을 바꿔준다.
				continue;
			}
			
			
			// 아래는 D의 경우
			
			// D 함수이면서 isRight가 true 일 경우
			if(isRight) {
				
				// 만약 반환 된 원소가 없을 경우 error를 출력하도록 하고 함수 종료
				if(deque.pollFirst() == null) {
					sb.append("error\n");
					return;
				}
				
			}
			else {
				// 만약 반환 된 원소가 없을 경우 error를 출력하도록 하고 함수 종료
				if(deque.pollLast() == null) {
					sb.append("error\n");
					return;
				}	
			}
		}
		
		// 모든 함수들이 정상적으로 작동했다면 덱의 남은 요소들을 출력문으로 만들어준다.
		makePrintString(deque, isRight);
		
	}
	
	public static void makePrintString(ArrayDeque<Integer> deque, boolean isRight) {
		
		sb.append('[');	// 여는 대괄호 먼저 StringBuilder에 저장
		
		if(deque.size() > 0) {	//만약 출력 할 원소가 한 개 이상일 경우
			
			if(isRight) {	// 정방향일경우 
				
				sb.append(deque.pollFirst());	// 먼저 첫 번째 원소를 넘겨준다.
				
				// 그 다음 원소부터 반점을 먼저 넘겨준 후 덱의 원소를 하나씩 뽑아 넘긴다. 
				while(!deque.isEmpty()) {
					sb.append(',').append(deque.pollFirst());
				}
			}
			else {	// 역방향일경우 
				sb.append(deque.pollLast());	// 먼저 뒤에서부터 첫 번째 원소를 넘겨준다.
				
				// 그 다음 원소부터 반점을 먼저 넘겨준 후 덱의 원소를 뒤에서부터 하나씩 뽑아 넘긴다. 
				while(!deque.isEmpty()) {
					sb.append(',').append(deque.pollLast());
				}
			}
		}
		
		sb.append(']').append('\n');	// 닫는 대괄호 및 개행으로 마무리
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

주석으로 과정을 모두 설명해놓았으니 크게 이해하는데 어려움은 없을 것이다.

 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

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

public class Main {

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {

		
		ArrayDeque<Integer> deque;
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		
		
		while(T --> 0) {
			
			String command = br.readLine();	// 문제에서 p에 해당하는 명령어
			int n = Integer.parseInt(br.readLine());
			
			/*
			 *  [a,b,c,...,x] 중 구분해야 할 것은 대괄호([, ])와 반점(,) 이다.
			 *  StringTokenizer로 여러 구분자를 사용 하고 싶다면
			 *  구분할 문자들을 합쳐서 넘겨주면 된다.
			 *  
			 *  만약 split()을 사용하고싶은 경우 정규식으로는
			 *  String input = br.readLine();
			 *  String[] s = input.subString(1, input.length - 1).split(","); 을 해주어야 한다.
			 *  
			 *  subString을 쓰지않고, split("[^0-9]") 또는, 
			 *  split("[\\[\\]\\,") 같이 정규식으로만 쓴다면 첫 번째 인자가 정규식에 걸려
			 *  빈 문자열을 반환하게 되기 때문
			 *  
			 *  ex)
			 *  str = "[1,2,3,4]";
			 *  strr[] = str.split("[\\[\\]\\,");
			 *  
			 *  result)
			 *  strr[0] = ""
			 *  strr[1] = "1"
			 *  strr[2] = "2"
			 *  strr[3] = "3"
			 *  strr[4] = "4"
			 */
			st = new StringTokenizer(br.readLine(), "[],");
			
			deque = new ArrayDeque<Integer>();
			
			// 덱에 배열 원소를 넣어준다.
			for(int i = 0; i < n; i++) {
				deque.add(Integer.parseInt(st.nextToken()));
			}
			
			AC(command, deque);
		}
		
		System.out.println(sb);
		
	}
	
	public static void AC(String command, ArrayDeque<Integer> deque) {
		
		boolean isRight = true;
		
		for(char cmd : command.toCharArray()) {
			
			if(cmd == 'R') {
				isRight = !isRight;	// 방향을 바꿔준다.
				continue;
			}
			
			
			// 아래는 D의 경우
			
			// D 함수이면서 isRight가 true 일 경우
			if(isRight) {
				
				// 만약 반환 된 원소가 없을 경우 error를 출력하도록 하고 함수 종료
				if(deque.pollFirst() == null) {
					sb.append("error\n");
					return;
				}
				
			}
			else {
				// 만약 반환 된 원소가 없을 경우 error를 출력하도록 하고 함수 종료
				if(deque.pollLast() == null) {
					sb.append("error\n");
					return;
				}	
			}
		}
		
		// 모든 함수들이 정상적으로 작동했다면 덱의 남은 요소들을 출력문으로 만들어준다.
		makePrintString(deque, isRight);
		
	}
	
	public static void makePrintString(ArrayDeque<Integer> deque, boolean isRight) {
		
		sb.append('[');	// 여는 대괄호 먼저 StringBuilder에 저장
		
		if(deque.size() > 0) {	//만약 출력 할 원소가 한 개 이상일 경우
			
			if(isRight) {	// 정방향일경우 
				
				sb.append(deque.pollFirst());	// 먼저 첫 번째 원소를 넘겨준다.
				
				// 그 다음 원소부터 반점을 먼저 넘겨준 후 덱의 원소를 하나씩 뽑아 넘긴다. 
				while(!deque.isEmpty()) {
					sb.append(',').append(deque.pollFirst());
				}
			}
			else {	// 역방향일경우 
				sb.append(deque.pollLast());	// 먼저 뒤에서부터 첫 번째 원소를 넘겨준다.
				
				// 그 다음 원소부터 반점을 먼저 넘겨준 후 덱의 원소를 뒤에서부터 하나씩 뽑아 넘긴다. 
				while(!deque.isEmpty()) {
					sb.append(',').append(deque.pollLast());
				}
			}
		}
		
		sb.append(']').append('\n');	// 닫는 대괄호 및 개행으로 마무리
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 27057269  -  방법 2 : BufferedReader

채점 번호 : 27057264  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

(StringBuilder을 사용하지 않고 매 번 출력을 하면 통과가 되려나..? 시도해봤더니 역시나 시간초과..)

 

 

 

---

• 정리

 

이 번 문제는 Deque만 알고있다면 알고리즘 자체가 어려운 건 아니였을 것이다.

 

다만, 입력에서 문자열 분리라던지, error 상황 처리에서 많이 걸렸을 것이라 생각이 든다.

 

혹여 위 풀이에서 이해가 가지 않거나 궁금한 점이 있다면 언제든 댓글 남겨주셔도 된다. :)