[백준/BOJ] 5430번 : AC (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

5430번: AC

---

- 문제 -

 

난이도 골드 5 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

R이 들어오면 배열을 뒤집고, D가 들어오면 맨 앞에 위치한 값을 제거해준다.

뒤집으려면 스택이 용이하고, 맨 앞에 위치한 값을 제거해주려면 큐가 더 좋다. 그렇기에 두개의 특성을 다 갖고있는 덱을 사용해 풀겟다.

 

[1,2,3,4,5]의 값이 왔고, RDRDD를 하라고 한다.

그렇다면 우선 R. [5,4,3,2,1]이 된다.

다음 D. [4,3,2,1]이 된다.

다음 R. [1,2,3,4]가 된다.

다음 D, D. 지우는게 두개이니 두개를 지우자. [3,4]가 된다.

쉽다 하지만. 이렇게하면 계속 뒤집는 과정에서 시간 초과가 날 수 있다. 그러니 매번 뒤집지 말고, 현재 배열이 뒤집힌 상태인지 뒤집히지 않은 상태인지를 파악하자.

예를 들면 R이 왔으면 이 배열은 뒤집힌 상태이고, 뒤에 R이 하나 더 오면 뒤집히지 않은 상태이다.

뒤집히고 값을 제거하면 뒤집히지 않은 상태에서 마지막 값을 제거한 것과 같은 효과를 볼 수 있다. 위에서 확인한 예를 보자.

R이 하나 와서 이 배열은 뒤집힌 상태이다.

D가 왔고, 뒤집힌 사태이니 맨뒤에 값을 지운다. [1,2,3,4]가 된다.

R이 하나 왔으니 뒤집한 상태에서 뒤집으니 뒤집지 않은 상태가 즉 원래대로 돌아온다. 

D가 왔다. 뒤집히지 않은 상태이니 맨 앞에 값을 제거한다. [2,3,4]가 된다.

D가 왔다. 위와 동일하니 맨 앞에 값을 제거한다. [3,4]

그리고 마지막으로 출력할때 실질적으로 배열은 한번도 뒤집지 않은 상태이기 때문에 현제 뒤집혀야하는지 뒤집히지 않아야하는지에 따라서 결과를 출력한다.

뒤집히지 않은 상태이니 [3,4] 그대로 출력한다.

즉 매번 뒤집지 말고, 지우기 전에 배열이 뒤집혀야하는지 뒤집혀지지 않아야하는지만 파악한 뒤 앞 또는 뒤에 값을 제거해준다.

마지막으로 에러형태를 보자. 에러는 어렵지 않다. 더 제거할 값이 없는데, 제거하라는 명령이 내려오면 에러가 나오게 되는 것이다.

 

코드를 보기전에 주의해야할 점들을 볼 것인데. 실제 필자가 풀면서 틀린 사유에 맞춰서 보겠다.

1. 출력 형태. 예제 출력을 보면 [2,1]이렇게 되어있다. 덱을 그대로 출력하면 [2, 1]로 출력된다. 같은 줄 알았지만 틀리고 나서 다시 보니 뛰어쓰기가 있으면 안되는 거였다. 반복문을 통해 하나하나 받아와서 출력하자.

2. 시간 초과. 테스트 케이스가 100이기에 그렇게 큰 차이가 없을것 같았는데, 덱을 하나하나 출력하다보니 시간 초과가 나게되는 것 같았다. StringBuilder를 사용하자.

3. 입력되는 값은 [1,2,3,4] 이런 식이다. 문자열로 받고, 1인덱스부터 홀수인 인덱스의 값만 받아왔다. 그렇다보니 10이상의 값들이 오게되면 그대로 받을 수가 없게 되는 것이였다. StringTokenizer로 [,]을 빼주고 토큰화해서 저장하자.

 

코드를 보자.

---

-풀이-

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < T; i++) {
			String p = br.readLine();
			int n = Integer.parseInt(br.readLine());
			Deque<Integer> deq = new LinkedList<Integer>();
			//뒤집힌 상태인지 확인하지위한 변수
			boolean reverse = false;
			//에러 여부를 확인하기위한 변수
			int error = 0;
			
			//입력받은 배열을 값만 빼서 토큰에 저장
			StringTokenizer st = new StringTokenizer(br.readLine(), "[,]");
			for(int j = 1; j < (n * 2); j += 2) {
				deq.offer(Integer.parseInt(st.nextToken()));
			}
			
			for(int j = 0; j < p.length(); j++) {
				if(p.charAt(j) == 'R') {
					if(reverse) reverse = false;
					else reverse = true;
				}else {
					//D가 왔는데 덱이 비어있으면 error에 1을 저장하고 반복 종료
					if(deq.isEmpty()) {
						error = 1;
						break;
					}
					if(reverse == false) deq.pollFirst();
					else deq.pollLast();
				}
			}
			
			if(error == 1) sb.append("error").append("\n");
			else {
				//reverse가 true면 뒤집힌 상태. 덱을 뒤집는 방법은 stack처럼
				//저장된 값을 맨 뒤 값부터 차례대로 제거 출력 해준다.
				if(reverse == true) {
					sb.append("[");
					while(!deq.isEmpty()) {
						sb.append(deq.pollLast());
						if(deq.isEmpty()) break;
						sb.append(",");
					}
					sb.append("]").append("\n");
				}else {
					sb.append("[");
					while(!deq.isEmpty()) {
						sb.append(deq.pollFirst());
						if(deq.isEmpty()) break;
						sb.append(",");
					}
					sb.append("]").append("\n");
				}
			}
		}
		System.out.println(sb);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.