[백준 14891] 톱니바퀴 (JAVA)

백준(BOJ) 14891 톱니바퀴

 

난이도
221222 기준 골드 5

사용 알고리즘
구현

문제 링크
https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있다.

 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.

...중략

 톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

 

입력

 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

 

출력

 총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

 

2. 어떤 알고리즘을 사용할 것인가

 

 구현문제는 어떤 자료구조를 사용할지 생각하는게 중요합니다. 이 문제는 톱니바퀴의 상태를 어느 자료구조에 담을지가 중요해 보입니다.

 톱니바퀴가 시계, 반시계 방향으로 움직이므로 앞뒤로 자유롭게 붙이고 뗄 수 있어야 할 것이고

 index로 톱니바퀴가 맞물린 왼쪽, 오른쪽 부분과 12시 부분을 찾는것 까지 고려하면 LinkedList를 사용하는게 좋아보입니다.

 

 

3. 풀이 구상

 

 K가 1~100이므로 100번을 직접 다 돌려도 시간초과는 일어나지 않을 것이므로 톱니바퀴를 돌리는 것만 구현하면 쉽게 풀릴듯 보입니다.

 톱니바퀴 클래스를 만들어서 톱니바퀴를 돌리면 앞뒤 톱니바퀴도 돌아갈 수 있는지 확인하고 돌아갈 수 있으면 돌리고.. 말로하면 복잡한데요

 처음에 몇 번 톱니바퀴를 어느 방향으로 돌릴지가 정해지면 그 톱니바퀴가 돌아가는 것에 따른 다른 톱니바퀴들의 움직임도 바로 결정이 됩니다. 따라서 현재 톱니바퀴 기준 오른쪽 왼쪽을 쭉 탐색하면서 이번 턴에 어떤 톱니바퀴들이 돌아갈지 결정을 해주고 현재 톱니바퀴가 시계방향이면 옆의 톱니바퀴는 반시계로 회전하는 것을 고려해서 어느 방향으로 돌아갈지까지도 정해주고나서 한 번에 톱니들을 돌리는 것을 반복하면 됩니다.

 이걸 코드로 구현하는 것이 조금 시간이 걸릴 것 같네요

 

4. 코드 작성

 

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

// 백준 14891번 톱니바퀴
public class Main {
	
	static Gear[] gears;
	
	static class Gear{
		
		int gearNum;
		
		LinkedList<Integer> sawList;

		public Gear(int gearNum, LinkedList<Integer> sawList) {
			this.gearNum = gearNum;
			this.sawList = sawList;
		}

		public void rotateInit(int direction) {
			// 오른쪽에 있는 애들 회전
			if(this.gearNum < 4) {
				if(this.sawList.get(2) != gears[this.gearNum+1].sawList.get(6)) {
					rotate(1,-direction);
				}
			}
			// 왼쪽에 있는 톱니들 회전
			if(this.gearNum > 1) {
				if(this.sawList.get(6) != gears[this.gearNum-1].sawList.get(2)) {
					rotate(-1,-direction);
				}
			}
			
			if(direction == 1) {
				this.sawList.offerFirst(this.sawList.pollLast());
			} else if(direction == -1) {				
				this.sawList.offerLast(this.sawList.pollFirst());
			}
		}

		public void rotate(int rl, int direction) {
			// 오른쪽이었으면 rl > 0
			if(rl>0) {
				if(this.gearNum+rl < 4) {
					if(gears[this.gearNum+rl].sawList.get(2) != gears[this.gearNum+rl+1].sawList.get(6)) {
						rotate(rl+1,-direction);
					}
				}
				if(direction == 1) {
					gears[this.gearNum+rl].sawList.offerFirst(gears[this.gearNum+rl].sawList.pollLast());
				} else if(direction == -1) {				
					gears[this.gearNum+rl].sawList.offerLast(gears[this.gearNum+rl].sawList.pollFirst());
				}
			}
			// 왼쪽이었으면 rl < 0
			if(rl<0) {
				if(this.gearNum+rl > 1) {
					if(gears[this.gearNum+rl].sawList.get(6) != gears[this.gearNum+rl-1].sawList.get(2)) {
						rotate(rl-1,-direction);
					}
				}
				if(direction == 1) {
					gears[this.gearNum+rl].sawList.offerFirst(gears[this.gearNum+rl].sawList.pollLast());
				} else if(direction == -1) {				
					gears[this.gearNum+rl].sawList.offerLast(gears[this.gearNum+rl].sawList.pollFirst());
				}
			}
		}
		
		@Override
		public String toString() {
			return this.sawList.toString();
		}
		
		
	}


    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    	// 0번 안 씀
    	gears = new Gear[5];
    	
    	for(int i = 1; i <= 4; i++) {
    		LinkedList<Integer> sawList = new LinkedList<>();
    		
    		String sawStr = br.readLine();
    		
    		for(int j = 0; j < 8; j++) {
    			sawList.add((sawStr.charAt(j)-'0'));
    		}
    		
    		Gear gear = new Gear(i, sawList);
    		gears[i] = gear;
    	}
    	
    	int rotCnt = Integer.parseInt(br.readLine());
    	
    	for(int i = 1; i <= rotCnt; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int num = Integer.parseInt(st.nextToken());
    		int direction = Integer.parseInt(st.nextToken());
    		
    		gears[num].rotateInit(direction);
    	}
    	
    	int resultPoint = 0;
    	for(int i = 1; i<=4; i++) {
    		if(gears[i].sawList.get(0)==1) {
    			resultPoint += (1<<(i-1));
    		}
    	}
    	
    	bw.write(resultPoint+"");
    	bw.flush();
        bw.close();
        br.close();
    }
    
 

}

 

 

2. 주의할 점

 

 정답은 한 번에 맞췄습니다. 다만, 회전 방향을 머릿속으로 생각하면 머리가 복잡해져서 노트에 써가면서 푸셔야 구현 문제를 푸실 때 시간을 단축 할 수 있습니다.

 처음 생각했던대로 LinkedList를 사용하였는데 적절한 선택이었습니다. 알고리즘 공부 할 때 자료구조를 많이 알아둘 수록 문제에서 어떤 자료구조를 사용해야 할지 감이 옵니다. 나중에 더 복잡하고 케이스의 크기가 커지는 문제가 나오면 어떤 자료구조를 선택하느냐에 따라 시간초과가 걸릴 수도 있기에 자료구조의 동작 원리도 잘 알아두시는게 좋을 것입니다.

 마지막에 점수 더 할 때는 깨알같은 비트연산을 써먹었습니다.

 

풀이 후기

  이번에도 백준 삼성 SW 역량테스트 문제집에 있는 문제를 풀어봤습니다. 삼성은 구현을 정말 중요시하네요