[백준] 15662.톱니바퀴(2) - Java

 

사용한 자료구조 및 개념 : LinkedList, Queue

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ 톱니바퀴를 회전시키기 위해 추가, 삭제할 수 있으면서 index가 있는 LinkedList를 사용하자.

• ArrayList는 내부적으로 배열로 되어 있기 때문에 추가 삭제 시 N만큼 다시 데이터를 복사, 붙여 넣기 해야 하지만,
• LinkedList는 추가, 삭제 시 해당하는 노드만 변경해 주면 되기 때문에 좀 더 효율적일 것 같다는 생각에 LinkedList를 사용하였다.

2️⃣ Queue를 사용하자.

• 왜냐하면 모든 톱니바퀴는 순차적이 아니라 동시에 회전하기 때문에
• 회전해야 하는 톱니바퀴와 방향을 확인 후, 큐에 담아주고
• 그 후에 큐에 담긴 톱니바퀴들을 한꺼번에 회전시켰다.

 

👻 어려웠던 점

🚨톱니바퀴들이 동시에 회전해야 하는 것을 어떤 자료 구조를 사용할 것인가를 처음에 좀 고민했다.

❗해결 : 아이디어에 적은 것과 같은 이유로 LinkedList와 Queue를 사용하여 해결하였다.

 

Solution Code & 주석

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

class Gear {
	int num, dir;

	public Gear(int num, int dir) {
		this.num = num;
		this.dir = dir;
	}
}

public class Main {

	static int T;
	static List<Integer>[] list;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());

		list = new LinkedList[T + 1];

		for (int t = 1; t <= T; t++) {
			String input = br.readLine();
			list[t] = new LinkedList<>(); // 초기화

			for (int i = 0; i < 8; i++) {
				list[t].add(input.charAt(i) - '0');
			}

		}

		int K = Integer.parseInt(br.readLine());

		for (int k = 0; k < K; k++) {
			st = new StringTokenizer(br.readLine());

			int num = Integer.parseInt(st.nextToken()); // 톱니바퀴 번호
			int dir = Integer.parseInt(st.nextToken()); // 회전 방향

			// 회전할 톱니바퀴 모두 큐에 담아줌.
			Queue<Gear> queue = checkGear(num, dir);

			// 큐에 담긴 톱니바퀴 모두 회전시킴.
			rotate(queue);
		}

		int cnt = 0;

		for (int i = 1; i <= T; i++) {
			if (list[i].get(0) == 1)
				cnt++;
		}

		System.out.println(cnt);
	}

	private static void rotate(Queue<Gear> queue) {

		while (!queue.isEmpty()) {
			Gear cur = queue.poll();

			// 시계방향
			if (cur.dir == 1) {
				// 마지막에 들어있는 극을 꺼냄.
				int pole = list[cur.num].remove(7);
				list[cur.num].add(0, pole);
			}
			// 반시계방향
			else {
				int pole = list[cur.num].remove(0);
				list[cur.num].add(7, pole);
			}
		}

	}

	private static Queue<Gear> checkGear(int num, int dir) {

		Queue<Gear> queue = new ArrayDeque<>();

		queue.offer(new Gear(num, dir));

		int frontNum = num;
		int frontDir = dir;
		int backNum = num;
		int backDir = dir;

		// num 톱니바퀴 왼쪽 방향으로 가며 추가로 회전시켜야 하는 톱니바퀴 확인
		while (--frontNum >= 1) {

			// 맞닿은 극이 같은 경우
			if (list[frontNum + 1].get(6) == list[frontNum].get(2))
				break;

			frontDir *= -1;
			queue.offer(new Gear(frontNum, frontDir));
		}

		// num 톱니바퀴 오른쪽 방향으로 가며 추가로 회전시켜야 하는 톱니바퀴 확인
		while (++backNum <= T) {

			// 맞닿은 극이 같은 경우
			if (list[backNum - 1].get(2) == list[backNum].get(6))
				break;

			backDir *= -1;
			queue.offer(new Gear(backNum, backDir));
		}

		return queue;
	}

}

 

마무리

문제를 읽고, 어떤 자료 구조를 활용하여 구현할 것인지 결정하는 게 오래 걸렸다.

그 이후에는 조건이 까다롭지 않아서 금방 구현할 수 있었다.