[백준] 14891번 : 톱니바퀴 - 자바[Java]

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

풀이

문제에 주어진대로 구현하는 문제다.

 

톱니바퀴의 상태가 String으로 주어지므로, 톱니바퀴의 상태를 저장하는 String[] 배열을 생성한다. N극, S극은 각각 0, 1로 저장된다.

여기서 핵심 인덱스는 2, 6번이다.

 

메서드

lotateClock(): 방향이 1이면  시계방향 -> 7번이 0번으로, newStr의 1~7번 인덱스 = str.substring(0, 7)

lotateCounterClock(): 방향이 -1이면 반시계 방향 -> 0번이 7번으로, newStr의 0~6번 인덱스 = str.substring(1, 8)

 

compareRight(): 현재 톱니바퀴 회전 후, 회전 전 톱니바퀴의 2번과 오른쪽에있는 6번 비교 -> 다르면 재귀호출
compareLeft(): 현재 톱니바퀴 회전 후, 회전 전 톱니바퀴의 6번과 왼쪽에있는 2번 비교 -> 다르면 재귀호출

 

초기 수도코드

static int size = 4;
String[] wheels = [4]

for () {
	현재 바퀴 num
	compareRight(num, dir)
	compareLeft(num, dir)
}

for(모든 톱니바퀴)
	if (str.charAt(0) == '1')
		score += Math.pow(2, i);

하지만 위 수도코드대로 코딩한 결과 틀린 답을 출력했다.

그 이유는 compareRight(), compareLeft()를 수행한 결과 현재 톱니바퀴를 두 번 돌리게 되기 때문이다.

이를 고치기 위해 compareRight()와 compareLeft()에 있는 현재 톱니바퀴 회전 로직과, 이후 톱니바퀴를 회전시키는지 판별하는 로직을 main()의 for문 내에 추가했다.

 

수정 한 수도코드

static int size = 4;
String[] wheels = [4]

for () {
	현재 바퀴 num

	if (dir == 1) lotateClock(num)
	else if (dir == -1) lotateCounterClock(num)

	if (num + 1 < 4 && 회전 전 2번 != 다음것 6번)
		compareRight(num+1, dir)
	if (num -1 >= 0 && 회전 전 2번 != 다음것 6번)
		compareLeft(num-1, dir)
}

for(모든 톱니바퀴)
	if (str.charAt(0) == '1')
		score += Math.pow(2, i);

 

코드

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

public class Main {
	
	static int size = 4;
	static String[] wheels = new String[4];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int i = 0; i < 4; i++) {
			wheels[i] = br.readLine();
		}
		
		int k = Integer.parseInt(br.readLine());
		while (k-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken()) - 1; // 1을 빼줘야한다.
			int dir = Integer.parseInt(st.nextToken());
			
			char curTwo = wheels[num].charAt(2);
			char curSix = wheels[num].charAt(6);
			
			// 현재 톱니바퀴 회전
			if (dir == 1) {
				lotateClock(num);
			} else if (dir == -1) {
				lotateCounterClock(num);
			}
			
			if (num + 1 < 4 && curTwo != wheels[num+1].charAt(6)) {
				compareRight(num+1, -dir); // 오른쪽 톱니바퀴 회전
			}
			if (num - 1 >= 0 && curSix != wheels[num - 1].charAt(2)) {
				compareLeft(num - 1, -dir); // 왼쪽 톱니바퀴 회전
			}
		}
		
		// 점수 계산
		int score = 0;
		for (int i = 0; i < size; i++) {
			if (wheels[i].charAt(0) == '1') {
				score += Math.pow(2, i);
			}
		}
		System.out.println(score);
	}
	
	public static void compareRight(int num, int dir) {
		char curTwo = wheels[num].charAt(2);
		
		// 현재 톱니바퀴 회전
		if (dir == 1) {
			lotateClock(num);
		} else if (dir == -1) {
			lotateCounterClock(num);
		}
		
		if (num + 1 < 4 && curTwo != wheels[num+1].charAt(6)) {
			compareRight(num+1, -dir); // 재귀호출
		}
	}
	
	public static void compareLeft(int num, int dir) {
		char curSix = wheels[num].charAt(6);
		
		// 현재 톱니바퀴 회전
		if (dir == 1) {
			lotateClock(num);
		} else if (dir == -1) {
			lotateCounterClock(num);
		}
		
		if (num - 1 >= 0 && curSix != wheels[num - 1].charAt(2)) {
			compareLeft(num - 1, -dir); // 재귀호출
		}
	}
	
	public static void lotateClock(int num) {
		String str = "";
		str += wheels[num].charAt(7);
		str += wheels[num].substring(0, 7);
		
		wheels[num] = str;
	}
	
	public static void lotateCounterClock(int num) {
		String str = wheels[num].substring(1, 8);
		str += wheels[num].charAt(0);
		
		wheels[num] = str;
	}
}

 

다른 풀이

- 현재 톱니바퀴를 회전시키는 로직을 lotate() 메서드로 추출했다.

- lotate() -> compare 순서가 아니라, compare부터 한 다음 lotate()함으로써 회전 전 톱니바퀴의 상태를 저장할 필요가 없어졌다. 또한 main() 메서드에서 중복되는 부분(현재 톱니바퀴 회전 로직과, 이후 톱니바퀴를 회전시키는지 판별하는 로직)을 제거하였다.

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

public class Main {
	
	static int size = 4;
	static String[] wheels = new String[4];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int i = 0; i < 4; i++) {
			wheels[i] = br.readLine();
		}
		
		int k = Integer.parseInt(br.readLine());
		while (k-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken()) - 1; // 1을 빼줘야한다.
			int dir = Integer.parseInt(st.nextToken());
			
			compareRight(num + 1, -dir); // 오른쪽 톱니바퀴 회전
			compareLeft(num - 1, -dir); // 왼쪽 톱니바퀴 회전
			lotate(num, dir); // 현재 톱니바퀴 회전
		}
		
		// 점수 계산
		int score = 0;
		for (int i = 0; i < size; i++) {
			if (wheels[i].charAt(0) == '1') {
				score += Math.pow(2, i);
			}
		}
		System.out.println(score);
	}
	
	public static void compareRight(int num, int dir) {
		if (num < 4 && wheels[num-1].charAt(2) != wheels[num].charAt(6)) {
			compareRight(num+1, -dir); // 재귀호출
			lotate(num, dir);
		}
	}
	
	public static void compareLeft(int num, int dir) {
		if (num >= 0 && wheels[num].charAt(2) != wheels[num+1].charAt(6)) {
			compareLeft(num - 1, -dir); // 재귀호출
			lotate(num, dir);
		}
	}
	
	public static void lotate(int num, int dir) {
		if (dir == 1) {
			lotateClock(num);
		} else if (dir == -1) {
			lotateCounterClock(num);
		}
	}
	
	public static void lotateClock(int num) {
		String str = "";
		str += wheels[num].charAt(7);
		str += wheels[num].substring(0, 7);
		
		wheels[num] = str;
	}
	
	public static void lotateCounterClock(int num) {
		String str = wheels[num].substring(1, 8);
		str += wheels[num].charAt(0);
		
		wheels[num] = str;
	}
}

 

위가 두번째 풀이, 아래가 첫번째 풀이. 코드 길이가 줄여진 것을 제외하고 유의미한 차이는 없다.