18115 : 카드 놓기 - JAVA

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

 

기본 Deque 문제이다.

Deque는 양방향으로 넣고 뺄 수 있다. 

처음에는 Deque를 쓰지 않고 ArrayList를 통해 문제를 풀려고 하였으나 탐색 과정 및 제거 과정이 시간을 많이 잡아먹어서 시간 초과가 났다. 그 뒤에 그냥 정석적으로 Deque를 사용하여 문제를 풀었다.

 

무조건 12 .. n 순서대로 카드가 정렬되므로 제시된 방법 반대로 하면 처음 카드 서순을 추적할 수 있다. 즉 역추적을 사용한다. 카드는 뒤로 쌓이고, 이미 된것을 되돌릴때는 역으로 해결하는 방법이 보편적이기 때문이다.

1번 같은 경우는 제일 아랫 카드를 내려놓고

2번 같은 경우는 뒤에서 두번째

3번 같은 경우는 제일 위의 카드를 내려놓는식으로 해결했다.

 

2번은 Deque가 맨 처음, 맨 끝에서만 들어갈 수 있으므로 임의의 int 변수를 만들어 기존 원소를 불러오고 해당 원소를 집어넣는 식, 즉 순서를 바꿔준다.

 

import java.util.*;
import java.io.*;
public class sol086 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Deque<Integer> dq = new LinkedList<>();
		ArrayList<Integer> list = new ArrayList<>();
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] command = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			command[i] = Integer.parseInt(st.nextToken());
		}
		int card = 1;
		for(int i = n-1; i >= 0; i--) {
			if(command[i] == 1) {
				dq.addLast(card);
			}
			if(command[i] == 2) {
				int temp = dq.getLast();
				dq.pollLast();
				dq.addLast(card);
				dq.addLast(temp);
			}
			if(command[i] == 3) {
				dq.addFirst(card);
			}
			card++;
		}
		for(int i = n-1; i >= 0; i--) {
			list.add(dq.poll());
		}
		for(int i = n-1; i>=0; i--) {
			bw.write(list.get(i) + " ");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}