문제

BOJ 15662: 톱니바퀴 (2) https://www.acmicpc.net/problem/15662

풀이

조건

• 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.
• 이 때, 회전 하기 전의 상태를 보고 회전 여부를 결정해야 한다.
  • 이 부분을 놓쳐서 시간 낭비를 했다.

풀이 순서

• 톱니바퀴의 12시 방향에 적힌 값을 시작으로 시계 방향 순으로 Deque에 넣는다.
  • 시계 방향, 반시계 방향 회전하고 난 뒤의 상태를 쉽게 구현하기 위해 Deque을 사용했다.
• 톱니바퀴의 번호와 그 상태를 HashMap에 저장한다.
• 명령을 입력 받을 때 마다 각 톱니바퀴의 오른쪽(3시)방향에 적힌 값과 왼쪽(9시)방향에 적힌 값을 배열에 미리 저장해둔다.
• 입력 받은 톱니바퀴를 기준으로 오른쪽, 왼쪽을 탐색하며 회전할 수 있는지 확인하고 배열에 기록한다.
• 회전한다.
• 12시 방향에 S극(1이 적혔는지)이 몇 개 적혀있는지 구한다.
  • 12시 방향을 기준으로 Deque에 값을 담아놨으므로 Deque의 First 값을 확인한다.

코드

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

public class Main {
    
	static int T;
	static HashMap<Integer, Deque<Integer>> deqMap; // 톱니바퀴 번호 대로 값을 넣을 HashMap
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	T = Integer.parseInt(br.readLine()); // 톱니 바퀴 갯수
    	
    	deqMap = new HashMap<>(); // 톱니 바퀴 넣을 HashMap
    	
    	// 1번 ~ T번 톱니바퀴 정보를 12시 방향부터 시계 방향으로 넣음
    	for(int i=1; i<=T; i++) {
    		String str = br.readLine();
    		Deque<Integer> deq = new ArrayDeque<>();
    		for(int j=0; j<8; j++) {
    			deq.addLast(str.charAt(j) - '0');
    		}
    		
    		deqMap.put(i, deq);
    	}
    	
    	
    	int K = Integer.parseInt(br.readLine()); // 회전 횟수
    	
    	for(int k=1; k<=K; k++) {
    		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    		
    		int deqNum = Integer.parseInt(st.nextToken()); // 선택된 톱니 바퀴의 번호
    		int rotDir = Integer.parseInt(st.nextToken()); // 회전 방향
    		
    		int[] rightNum = new int[T+1]; // 톱니바퀴의 오른쪽에 적힌 값을 넣는 배열
    		int[] leftNum = new int[T+1]; // 톱니바퀴의 왼쪽에 적힌 값을 넣는 배열
    		
    		// 각 톱니바퀴의 오른쪽, 왼쪽 값을 배열에 저장
    		for(int i=1; i<=T; i++) {
    			Deque<Integer> deq = deqMap.get(i);
    			
    			Iterator<Integer> itr = deq.iterator();
    			for(int t=0; t<=6; t++) {
    				int num = itr.next();
    				if(t == 2) {
    					rightNum[i] = num;
    				}
    				if(t == 6) {
    					leftNum[i] = num;
    				}
    			}
    		}
    		
    		// 각 톱니바퀴가 회전을 해야하는지 체크
    		// 배열에 회전 가능한 톱니바퀴와 회전 방향을 넣음
    		boolean[] isRot = new boolean[T+1]; // 회전 시킬 수 있으면 true 넣을 배열
    		int[] turnDir = new int[T+1]; // 회전 시킬 수 있는 톱니바퀴의 회전 방향을 넣을 배열
    		
    		isRot[deqNum] = true;
    		turnDir[deqNum] = rotDir;
    		// 입력 받은 톱니바퀴 기준으로 오른쪽 확인
    		int nDir = rotDir;
    		for(int i=deqNum; i<=T-1; i++) {
    			if(rightNum[i] != leftNum[i+1]) {
    				isRot[i+1] = true;
    				turnDir[i+1] = (nDir == 1 ? -1 : 1);
    				nDir = turnDir[i+1];
    			} else {
    				break;
    			}
    		}
    		// 입력 받은 톱니바퀴 기준으로 왼쪽 확인
    		nDir = rotDir;
    		for(int i=deqNum; i>=2; i--) {
    			if(leftNum[i] != rightNum[i-1]) {
    				isRot[i-1] = true;
    				turnDir[i-1] = (nDir == 1 ? -1 : 1);
    				nDir = turnDir[i-1];
    			} else {
    				break;
    			}
    		}
    		
    		// 회전 시작
    		for(int i=1; i<=T; i++) {
    			if(isRot[i]) {
    				Deque<Integer> deq = rotateDeq(i, turnDir[i]);
    				
    				deqMap.remove(i);
    				deqMap.put(i, deq);
    			}
    		}
	
    	}
    	
    	// 12시 방향 S극(1) 갯수 구하기
    	int sum = 0;
    	for(int i=1; i<=T; i++) {
    		Deque<Integer> deq = deqMap.get(i);
    		int num = deq.peekFirst();
    		if(num == 1) {
    			sum++;
    		}
    	}
    	
    	System.out.println(sum);
    }
   
    
    // 명령에 따라 톱니바퀴 회전
    static Deque<Integer> rotateDeq(int deqNum, int rotDir) {
    	Deque<Integer> deq = deqMap.get(deqNum);
    	
    	// 시계 방향 회전
    	if(rotDir == 1) {
    		int n = deq.pollLast();
    		deq.addFirst(n);
    	} 
    	// 반시계 방향 회전
    	else if(rotDir == -1) {
    		int n = deq.pollFirst();
    		deq.addLast(n);
    	}
    	
    	return deq;
    }
    
}

정리

• 문제 이해를 잘 못 해서 시간을 낭비했다.