[백준] 단계별로 풀어보기(단계:19,큐/덱,JAVA)5430번, AC

문제 링크

5430번: AC

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 덱은 큐(FIFO), 스택(LIFO)처럼 나오는 순서가 한 곳으로 한정된 것이 아닌 양방향에서 출력할 수 있는 자료구조입니다. 그래서 스택으로 사용할 수도 있고 큐로 사용할 수 있는 자료구조입니다.

예를 들어 3, 2, 1을 순서대로 덱에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 3을 덱에 넣었을 때

3

2. 2을 덱에 넣었을 때

3

2

3. 1을 덱에 넣었을 때

3

2

1

4. 덱에서는 자료를 출력할 때 First인지 Last인지 정할 수 있습니다.

First인 경우

3

2

1

Last인 경우

3

2

1

5. 결과

First인 경우

2

1

Last인 경우

3

2

위에 표를 보면서 덱은 First와 Last를 구분하여 저장 및 출력할 수 있습니다.

Java에서 덱를 표현하려면 ArrayDeque<>()로 선언해주어야 하므로 덱을 선언해주었습니다.

명령어를 입력받고 그에 해당하는 배열에 대하여 AC함수를 실행하고 남은 배열에 값을 출력하는 문제입니다.

이 문제에서 배열에 내용을 배열에 저장하여 'R' 명령어를 실행할 때마다 배열에 값들을 뒤집어주는 알고리즘을 선택했을 때 시간초과가 발생합니다.

그래서 데크를 사용하여 뒤집어주지 않고 pollFirst()와 pollLast()을 사용하여 뒤집어주는 과정을 생략하는 알고리즘을 사용하였습니다.

알고리즘은

1. 입력값 및 데크를 초기화를 진행합니다.

2. 명령어에서 'R'이 나오면 boolean형식을 사용하여 배열이 뒤집어졌는지 확인하도록 하였습니다.

3. 뒤집어지지 않았다면 pollFirst()을 진행하고 뒤집어졌다면 pollList()을 사용하였습니다.

4. 명령어를 모두 실행한 뒤에 뒤집어졌는지에 대한 결과에 따라서 남아있는 데크에 값들을 출력하였습니다.

5. 위 과정을 반복하여 여러 AC함수에 대한 결과를 구하였습니다.

6. 에러를 처리할 때에는 'D'가 나왔을 때 데크가 비어있으면 처리하도록 하였습니다.

예제입력에 첫 번째를 살펴보면

명령어 : RDD

배열 : [1,2,3,4]입니다.

1. 명령어 'R'실행

isRight = true -> false

1

2

3

4

2. 명령어 'D'실행

isRight = false

isRight가 false이므로 pollLast() 실행

1

2

3

4

3. 명령어 'D'실행

isRight = false

isRight가 false이므로 pollLast() 실행

1

2

3

4. 마지막 남아있는 데크 값 출력

1

2

isRight = false

isRight가 false이므로 pollLast()로 남아있는 데크 값들 출력

결과 = [2,1]

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 배열의 값을 '[],' 기준으로 나누었습니다.
• 명령어 수행 및 남은 데크 결과 출력하는  commandCheck/AC 함수를 만들었습니다.
• BufferedWriter에 남은 데크의 결과를 저장한 StringBuilder를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• commandCheck 함수는 위 알고리즘처럼 'R'일 때 isRight를 변경해주었고 'D'일 때는 isRight에 따라 데크의 값들을 poll() 해주었습니다.
• AC는 isRight와 empty를 이용하여 남아있는 데크에 값들을 StringBuilder에 추가하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Deque<Integer> deque = new ArrayDeque<>();	//배열 저장 데크
	static StringBuilder sb;	//결과 저장 StringBuilder
	static boolean empty;		//데크 비어있는지 확인
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //값 출력하는 BufferedWriter
        //-----------입력값 저장 및 데크 초기화--------
        int index = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0;i<index;i++) {
        	sb = new StringBuilder();
        	String command = br.readLine();
        	int arrSize = Integer.parseInt(br.readLine());
        	st = new StringTokenizer(br.readLine(), "[],");
        	//데크 초기화
        	for(int j=0;j<arrSize;j++) 
        		deque.offer(Integer.parseInt(st.nextToken()));
        	
        	empty = false;
            //함수 실행
        	boolean isRight = commandCheck(command);
        	AC(isRight);
        	
        	bw.write(sb.toString() + "\n");	//결과 BufferedWriter에 저장
        	deque.clear();		//데크 초기화
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //-------------명령어 실행하는 함수--------
    public static boolean commandCheck(String command) {
    	boolean isRight = true;
    	for(int j=0;j<command.length();j++) {
    		if(command.charAt(j)=='R')	//명령어가 R인 경우
    			isRight = !isRight;
    		if(command.charAt(j)=='D') {	//명령어가 D인 경우
    			if(deque.isEmpty()) {	//데크가 비어있을 때
    				empty = true;	
    				break;
    			}
    			if(isRight)
    				deque.pollFirst();
    			else
    				deque.pollLast();
    		}
    	}
    	return isRight;
    }
    //------------AC 함수 결과 반환하는 함수------
    public static void AC(boolean isRight) {
    	int size = deque.size();
    	if(empty) {	//데크가 비어있으면 오류처리
    		sb.append("error");
    	}else{
        //-----------데크 결과 StringBuilder에 저장---------
    		sb.append("[");
    		if(isRight){
        		for(int j=1;j<size;j++)
        			sb.append(deque.pollFirst() + ",");
        		
        		if(deque.peek()!=null)
            		sb.append(deque.poll());
    		}else {
    			for(int j=1;j<size;j++) 
    				sb.append(deque.pollLast() + ",");
    			
    			if(deque.peek()!=null)
    				sb.append(deque.poll());
    		}
    		sb.append("]");
    	}
    }
}