[SWEA] JAVA - 3499 퍼펙트 셔플

(설명 오늘내로 업로드 예정입니다!!!)

 

 

N개의 카드가있으면 이를 정확하게 반으로 나누고 나눈것들을 교대로 카드를 뽑아 새로운 덱을 만드는 문제이다. 이때 반으로 나눈 카드들을 각각 맨 앞에 있는 카드를 먼저 뽑아야 한다. 맨 앞에 있는 카드를 먼저 뽑아야 하는 순서를 지켜야 하기 때문에 Queue 를 활용하여 풀었다.

 

이때 N이 홀수일경우 먼저 놓는쪽에 한장이 더 들어가게 처리해줘야 하기 때문에 N이 짝수인 경우와 홀수인 경우를 나눠서 처리해줬다.

 

1. 카드를 반으로 나눈것들중 왼쪽의 카드와 오른쪽의 카드를 저장하기 위한 left, right 큐를 만들었다.

2. left 큐에서 한장뽑은다음 right 큐에서 한장을 한쪽의 큐가 모두 비어있을때까지 반복해주었다.

3. 이렇게 뽑힌 카드들의 순서를 저장하는 것도 큐로 만들어주었다.(배열로 해도 상관없다) 

 

package com.java.algorithm;

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

public class SWEA_3499_퍼펙트셔플 {
	static Queue<String> left;
	static Queue<String> right;
	static Queue<String> result;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC =Integer.parseInt(br.readLine());
		for (int t = 1; t <= TC; t++) {
			int N =Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			result = new LinkedList<String>();
			left = new LinkedList<String>();
			right = new LinkedList<String>();
			if(N%2==0) {
				for (int i = 0; i < N/2; i++) {
					left.add(st.nextToken());
				}
				for (int i = N/2; i < N; i++) {
					right.add(st.nextToken());
				}
			}else {
				for (int i = 0; i <= N/2; i++) {
					left.add(st.nextToken());
				}
				for (int i = N/2+1; i < N; i++) {
					right.add(st.nextToken());
				}
			}
			
			while(result.size() < N) {
				result.add(left.poll());
				result.add(right.poll());
			}
			
			
			sb.append("#").append(t).append(" ");
			for (int i = 0; i < N; i++) {
				sb.append(result.poll()).append(" ");
			}
			sb.append("\n");
			
		}
		System.out.print(sb);


	}

}