[JAVA] 백준 14891 톱니바퀴 (+ SWEA 4013 특이한 자석)

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

14891번: 톱니바퀴

 

1. 서론

 

엄청 어려워 보이는 데 찬찬히 읽어보면 쉬운 문제이다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH 

SW Expert Academy

SWEA의 모의 SW 역량테스트인 특이한 자석 문제와 입출력 형식만 제외하고는 정말 같은 문제이다.

(모의 SW 역량테스트는 삼성 A형 수준의 문제라는건데 솔직히 요즘 A형 수준 너무 올라가서 이 정도 수준 절대 아님)

 

2. 문제 풀이

 

4개의 톱니바퀴가 주어진다. 톱니바퀴는 8개의 톱니로 나뉘어 있다. 각 톱니는 S극 혹은 N극이다.

 

4개 중 한 개의 바퀴를 시계방향 혹은 반시계방향으로 돌린다.

 

이때 양쪽의 맞물려있는 바퀴가 서로 극이 다르면 원래 돌리려는 바퀴와 반대방향으로 돌아간다.

 

원래 바퀴에 의해 양쪽 바퀴가 돌아가면 그 양쪽 바퀴의 양쪽에 있는 바퀴도 영향을 받아서 돌아간다.

 

(내가 헷갈렸던 부분은 양쪽에 같은 극이 있다면 원래 바퀴는 안 도는 건가? 생각했는데 양쪽 극 상관없이 돌리기로 한 바퀴는 무조건 돈다.)

 

바퀴가 도는 원리와 그걸 구현하는 방법을 생각해내는 것이 포인트다.

처음에는 그냥 4개 밖에 없으니까 양쪽 돌리고 나머지 하나 처리하면 되겠지? 단순하게 생각했는데 그러면 예외가 발생한다.

 

 

 

 

그래서 내가 생각한 방법은 선택된 바퀴를 기준으로 순서대로 바퀴를 돌리는 방법이다.

예를 들어 2번 바퀴가 선택됐다면 2번을 기준으로 순서대로 3, 4번을 순서대로 탐색한다. 만약 중간에 돌아가지 않은 바퀴가 나오면 즉시 탐색을 멈춘다. 그리고 반대방향인 1번 바퀴 쪽으로 탐색을 진행하고 똑같이 돌아가지 않는 바퀴가 나오면 탐색을 멈추게 했다.

그래서 이와같이 바퀴를 전부 돌면서 돌릴 바퀴를 체크하는 배열을 만들었고 이 배열을 토대로 바퀴를 시계 혹은 반시계 방향으로 돌렸다.

 

처음에 톱니를 보고 톱니를 어떻게 구현할까? 고민했다. 톱니의 특성인 원형을 그냥 배열로 구현하기에는 어려워 큐를 써야겠다고 생각했다.

왜냐하면 톱니가 빙글 앞뒤로 도는 게 앞, 뒤로 값을 왔다 갔다 이동하는 형태였기 때문이다. 근데 그냥 큐는 앞의 값을 빼고 뒤로 넣는 형태이기 때문에 뒤의 값을 앞으로 넣어야 하는 이 문제에는 적절하지 않았다. 그래서 어떻게 할까 고민하다가 LinkedList(연결리스트)를 활용해 문제를 풀었다. LinkedList는 앞의 값을 빼서 뒤에 넣는 큐의 형태와 더불어 뒤의 값을 빼서 앞에 넣는 것도 가능하고, 배열처럼 특정 index값도 불러올 수 있기 때문에 이 문제를 풀기에 아주 적합한 자료구조다!

 

 

 

 

3. 코드 설명

 

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

public class Main {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		LinkedList list[] = new LinkedList[5]; //톱니 바퀴 4개 (1~4, 0은 버림)
		for (int i = 1; i <= 4; i++) {
			String s = br.readLine();
			LinkedList<Integer> t = new LinkedList<>();
			for (int j = 0; j < 8; j++)
				t.add(s.charAt(j) - '0');
			list[i] = t;
		}
		
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()); // 톱니 번호
			int y = Integer.parseInt(st.nextToken()); // 도는 방향
			
			int[] check = new int[5]; //톱니바퀴 체크, -1은 반시계, 1은 시계방향
			check[x] = y;
			
			int c = y;
			for (int j = x + 1; j <= 4; j++) { //오른쪽 체크
				if (list[j].get(6) != list[j - 1].get(2)) { //6번은 왼쪽 끝, 2번은 오른쪽 끝값이다
					c *= -1; //원래 바퀴 기준으로 반대방향이어야 하므로
					check[j] = c;
				}
				else break; //그만도는 순간 멈춘다
			}
			
			c = y;
			for (int j = x - 1; j >= 1; j--) { //왼쪽 체크
				if (list[j].get(2) != list[j + 1].get(6)) {
					c *= -1;
					check[j] = c;
				}
				else break;
			}

			for (int j = 1; j <= 4; j++) {
				if (check[j] == 1) // 시계방향, 뒤를 앞으로
					list[j].addFirst(list[j].pollLast());
				if (check[j] == -1) // 반시계 방향, 앞을 뒤로
					list[j].addLast(list[j].pollFirst());
			}
		}
		
		int sum = 0;
		for (int i = 1; i <= 4; i++)
			if (list[i].get(0) == (Object)1) //0은 12시 방향
				sum += 1 * Math.pow(2, i - 1); // 1, 2, 4, 8은 2의 i - 1승이다.
		
		System.out.println(sum);	
	}
}

 

주석 참조!!

 

LinkedList 맨날 그냥 큐만드는 용으로 썼는데 아주 효자구나!! 덕분에 문제 간결하게 풀었다 ㅎㅎ 고맙다 LinkedList야

풀이를 작성하고 다른 사람들은 어떻게 풀었나 찾아봤는데 int형 배열로 받아서 수동으로 배열의 값을 옮기고 있다...

이렇게 푼 사람.... 진짜 나 뿐이야? 메모리는 많이 들지만 쉽고 좋은데...

 

 

 

 

+ SWEA 코드

 

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

public class Solution {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			int n = Integer.parseInt(br.readLine());
			
			LinkedList list[] = new LinkedList[5];
			for (int i = 1; i <= 4; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				LinkedList<Integer> t = new LinkedList<>();
				while(st.hasMoreTokens())
					t.add(Integer.parseInt(st.nextToken()));
				list[i] = t;
			}
			
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				int[] check = new int[5]; //톱니바퀴 체크
				check[x] = y;
				
				int c = y;
				for (int j = x + 1; j <= 4; j++) { //오른쪽 체크
					if (list[j].get(6) != list[j - 1].get(2)) {
						c *= -1;
						check[j] = c;
					}
					else break;
				}
				
				c = y;
				for (int j = x - 1; j >= 1; j--) { //왼쪽 체크
					if (list[j].get(2) != list[j + 1].get(6)) {
						c *= -1;
						check[j] = c;
					}
					else break;
				}
	
				for (int j = 1; j <= 4; j++) {
					if (check[j] == 1)
						list[j].addFirst(list[j].pollLast());
					if (check[j] == -1)
						list[j].addLast(list[j].pollFirst());
				}
			}
			
			int sum = 0;
			for (int i = 1; i <= 4; i++)
				if (list[i].get(0) == (Object)1)
					sum += 1 * Math.pow(2, i - 1);
			
			sb.append("#" + tc + " " + sum + "\n");
		}
		System.out.println(sb.toString());
	}
}

 

입출력만 다르지만 혹시 몰라 볼 사람들 보라고 첨부