백준 15500번: 이상한 하노이 탑

문제 설명

• https://www.acmicpc.net/problem/15500
• 규칙이 적용되지 않는 하노이 탑 문제입니다.
  단순히 왼쪽의 도형을 순서대로 오른쪽에 넣는 방법에 대해 고민하는 문제입니다.

접근법

• 스택(정확히는 덱)을 이용해 문제를 풀었습니다.
• 현재 놓아야 할 가장 큰 판(targetNum)이 어떤 것인지를 구합니다.
• 가장 큰 판이 첫번째 봉에 있는지 두번째 봉에 있는지를 구합니다.
• 해당 봉에서 targetNum에 해당하는 봉이 나올때까지 나머지 봉으로 판을 옮깁니다.
• targetNum을 세번째 봉으로 옮기고 targetNum을 1 감소시킵니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int targetNum = N;
		int cnt = 0;
		StringBuilder sb = new StringBuilder();
		LinkedList<Integer> First = new LinkedList<Integer>();
		LinkedList<Integer> Second = new LinkedList<Integer>();
		StringTokenizer st = new StringTokenizer(br.readLine());

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

		while (targetNum > 0) {
			if (First.contains(targetNum)) {
				while (First.size() > 0) {
					int now = First.pollLast();
					if (now == targetNum) {
						sb.append("1 3\n");
						cnt++;
						targetNum--;
						break;
					} else {
						sb.append("1 2\n");
						cnt++;
						Second.add(now);
					}
				}
			} else if (Second.contains(targetNum)) {
				while (Second.size() > 0) {
					int now = Second.pollLast();
					if (now == targetNum) {
						sb.append("2 3\n");
						cnt++;
						targetNum--;
						break;
					} else {
						sb.append("2 1\n");
						cnt++;
						First.add(now);
					}
				}
			}
		}
		System.out.println(cnt);
		System.out.println(sb.toString());
	}

}