/ SWEA

SWEA_3499_퍼펙트셔플_JAVA

문제 : 퍼펙트셔플

SWEA문제는 로그인을 해야 열람할 수 있습니다.

링크 : SWEA_3499_퍼펙트셔플

접근 방식

A B C D E F가 있다고 한다면, 이를 A,B,C D,E,F으로 나누어서 A,D,B,E,C,F으로 교차하여 새로운 카드모음을 만들어야한다. 기존문자열이 홀수일 경우는 먼저 놓는 쪽에 한 장을 추가한다.

이 문제는 여러 방식으로 풀어볼 수 있는데, 나는 스택&덱과 링크드리스트를 이용해서 풀었다. 여기서는 스택과 덱을 이용해서 풀어볼 것이다.

먼저 주어진 문자열을 중간을 기준으로 절반으로 분리한다.

2개의 문자열이 생기면, 앞에 있던 문자열과 뒤에 있던 문자열을 번갈아가면서 스택에 넣는다. 만약 문자열의 전체 길이가 홀수라면, 앞에 있는 문자열을 1번 더 넣어준다.

모든 문자열이 스택에 푸시가 되었다면, 덱을 생성하고, 스택에서 하나씩 꺼내 front로 값을 집어넣는다.

완성덴 덱을 출력해준다.

풀이 방법

  1. 먼저 스택 2개를 생성한다.(스택1, 스택2), 또 덱을 하나 선언하여 주어진 문자열을 모두 담는다.

  2. 전체 문자열의 절반, 덱에서 문자열을 꺼내어 스택1에 담는다.

  3. 덱부터 시작하여 번갈아가며 덱과 스택 1에 있는 값을 스택 2에 담는다.

  4. 스택 2에 들어간 값을 덱에 앞에서부터 담는다.

  5. 덱에서 순서대로 꺼내 출력한다.

소스 코드


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

public class D3_3499_퍼펙트셔플 {

	// 1번쨰 방법 스택으로 자르고, 스택에 번갈아가면서 넣은 뒤에 덱으로 앞에서부터 넣기
	public static void main(String[] args) throws NumberFormatException, IOException {

		System.setIn(new FileInputStream("input_3499.txt"));

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(in.readLine());

			StringTokenizer st = new StringTokenizer(in.readLine(), " ");

			Deque<String> que = new LinkedList<>();
			Stack<String> stack = new Stack<>();
			Stack<String> stack2 = new Stack<>();

			for (int i = 0; i < N; i++) {
				que.add(st.nextToken());
			}

			// 절반 스택1에 꺼내기
			for (int i = 0; i < N / 2; i++) {
				stack.push(que.removeLast());
			}
			// 번갈아가면서 스택2에 집어넣기
			for (int i = 0; i < N / 2; i++) {
				stack2.push(que.pollFirst());
				stack2.push(stack.pop());
			}
			// 홀수일 때
			if (que.size() % 2 == 1) {
				// 홀수일때는 원래 들어있던 값이 1개 더 많기 때문에 한 번 더 집어넣어주기
				stack2.push(que.pollFirst());
			}
			// 스택2에 있는 값 차례대로 덱에 앞에서부터 집어넣기
			for (int i = 0; i < N; i++) {
				que.offerFirst(stack2.pop());
			}

			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < N; i++) {
				sb.append(que.remove()).append(" ");
			}

			System.out.printf("#%d %s\n", tc, sb);

		}

	}

아래는 2번째 방법인 링크드리스트를 이용해서 구현한 코드이다.


// 2번 방법 : 스택으로 꺼내서 저장하고, 값은 LinkedList로 중간에 삽입한다.
public static void main1(String[] args) throws NumberFormatException, IOException {

	System.setIn(new FileInputStream("input_3499.txt"));

	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

	int T = Integer.parseInt(in.readLine());

	for (int tc = 1; tc <= T; tc++) {
		int N = Integer.parseInt(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		LinkedList<String> que = new LinkedList<>();
		Stack<String> stack = new Stack<>();

		for (int i = 0; i < N; i++) {
			que.add(st.nextToken());
		}

		// 이 때는 짝수 홀수 구분 안해도 잘 돌아간다.

		// 절반 꺼내기
		for (int i = 0; i < N / 2; i++) {
			stack.push(que.removeLast());
		}
		// LinkedList에 index 통해서 삽입
		for (int i = 0; i < N; i++) {
			if (i % 2 == 1) {
				que.add(i, stack.pop());
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			sb.append(que.remove()).append(" ");
		}

		System.out.printf("#%d %s\n", tc, sb);

	}

}

}