Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

7. AC

5430번

덱을 활용하여 시간복잡도를 향상시키는 문제

이번 문제는 배열에 있는 숫자의 순서를 뒤집는 함수 R과, 첫 번째 숫자를 버리는 함수 D가 있는 정수 배열에 연산을 하기 위해 만든 언어 AC를 이용해서 푸는 문제입니다. 이번 문제는 덱(Deque) 자료구조를 이용하여 풀 수 있습니다.

• Java

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());

			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 is_right = true;
		
		for(char cmd : command.toCharArray()) {
			
			if(cmd == 'R') {
				is_right = !is_right;	// 방향을 바꿔준다.
				continue;
			}			
			
			// 함수 D			
			if(is_right) {	// D 함수이면서 isRight가 true 일 경우
				
				// 반환 된 원소가 없는 경우 error를 출력
				if(deque.pollFirst() == null) {
					sb.append("error\n");
					return;
				}
				
			}else {
				// 반환 된 원소가 없는 경우 error 출력
				if(deque.pollLast() == null) {
					sb.append("error\n");
					return;
				}	
			}
		}
		
		makePrintString(deque, is_right);
		
	}
	
	public static void makePrintString(ArrayDeque<Integer> deque, boolean is_right) {
		
		sb.append('[');	
		
		if(deque.size() > 0) {	// 출력 할 원소가 한 개 이상
			
			if(is_right) {	// 정방향일n경우 
				
				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');
	}
}

• Python

import sys
def AC(cmd,n, deque):
    cmd.replace('RR', '')
    l, r, d = 0, 0, True
    for c in cmd:
        if c == 'R': d = not d
        elif c == 'D':
            if d: l += 1
            else: r += 1
    if l+r <= n:
        res = deque[l:n - r]
        if d: return '[' + ','.join(res) + ']\n'
        else: return '[' + ','.join(res[::-1]) + ']\n'
    else:
        return 'error\n'

T = int(sys.stdin.readline())
for _ in range(T):
    cmd = sys.stdin.readline()
    n = int(sys.stdin.readline())
    deque = sys.stdin.readline().rstrip()[1:-1].split(',')
    if n == 0 : []
    sys.stdout.write(AC(cmd, n, deque))