링크

문제 링크

문제 설명 (길어서 요약)

왼쪽부터 차례대로 1번, 2번, 3번, 4번 톱니바퀴다.

여기서부터 이제 N번째 톱니바퀴를 시계, 반시계 방향으로 회전을 할껀데

여기 초록색 점선의 극들이 맞물려서 회전하는 배경이다.

주요 로직은 "톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다." 는 것이다. 위에 그림을 살펴보자!

예를 들어서 현재 3번 톱니바퀴를 반시계 방향으로 회전한다면 이렇게 된다.

문제 설명이 솔직히 좀 정확하지 않아서 좀 쉽게 핵심만 풀어서 쓰자면 3번을 선택했을 때, 그 주변 톱니바퀴(2번, 4번)이랑 맞물린 극을 비교해서 다르면 그 바퀴들을 3번의 방향과 반대방향으로 회전시키고 그 후 3번도 마저 회전시킨다.

그래서 최종 회전이 다 끝나고나서 북쪽을 가리키고있는 극에 따라 점수를 내는 문제다.

입력

첫째 줄에 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점

입출력 예제

풀이

1. 톱니바퀴 시계 반시계 회전을 시간복잡도 낮게 표현하기 쉽도록 4개의 연결리스트로 관리했다.
2. 회전은 재귀로 구현했는데, visited를 표시해서 왼쪽갔다가 오른쪽갔다가 다시 왼쪽가는 에러가 생기지않게끔하자.
3. 재귀로 표현하다보니 안쪽에 조건문이 좀 복잡해졌다. 인덱스(now)를 벗어나지 않으며, !visited이면서 now - 1 또는 now + 1과 맞물린 극이 다르면 rotate를 시켜준다.
4. 각 입력마다 회전시켜주고 끝나면 점수 계산해주기!

문제를 내 마음대로 해석해서 풀다가 좀 해맸다 ㅋㅋㅋ

다른 사람들의 풀이를 보면 백줄이 넘어가는 풀이가 보이는데 아마 회전을 일일이 다 구현했을 것 같다...

그렇게 하기 싫어서 단순한 재귀로 구현했는데, 이 문제에 한정해서 수정하기도 편했다.

기존 코드는 선택된 톱니바퀴를 회전시킨 후에 다음 rotate 조건을 살폈는데 이렇게 하니까 3번 예제가 통과가 안되는거다!

그래서 내가 손으로 3번 예제를 해봤는데 분명 코드는 내 의도대로 돌아가고있었다.

그 말은 즉슨! 내가 문제 이해를 어딘가 잘못했다는 뜻!

그래서 문제를 다시 찬찬히 살펴보았는데도 솔직히 설명이 좀 부족해보였다.

역시나 나와 같은 고민을 한 사람들이 꽤나 있었고 그 사람들의 질문을 보며 문제를 명확히 이해했다.

기존 로직 -> 선택된 톱니바퀴를 회전시킨 후 다음 rotate
변경 로직 -> 회전시키지 않고 현재 rotate를 찾고 마지막에 회전시킨다.

프로그래머스 풀 때는 이런 문제가 없었는데 유난히 백준 문제는 설명이 좀 불친절하게 느껴진다....!! ㅜㅜ

코드

package Sample;
import java.util.*;
public class Main {
	static boolean[] visited;
	public static void rotate(ArrayList<LinkedList<Integer>> q , int now, int dir) {
		visited[now] = true;
		if(now > 0 && !visited[now - 1] && q.get(now).get(6) != q.get(now - 1).get(2)) { //자신의 왼쪽 톱니
			rotate(q, now - 1, dir * -1);
		}
		if(now < 3 && !visited[now + 1] && q.get(now).get(2) != q.get(now + 1).get(6)) {
			rotate(q, now + 1, dir * -1);
		}
		switch(dir) {
		case 1:
			q.get(now).addFirst(q.get(now).removeLast());
			break;
		case -1:
			q.get(now).addLast(q.get(now).removeFirst());
			break;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<LinkedList<Integer>> q = new ArrayList<>(4);
		visited = new boolean[4];
		for(int i = 0; i < 4; i++) {
			String s = sc.next();
			LinkedList<Integer> temp = new LinkedList<>();			
			for(int j = 0; j < s.length(); j++) {
				if(s.charAt(j) == '1')
					temp.add(1);
				else
					temp.add(0);
			}
			q.add(temp);
		}
		int K = sc.nextInt();
		for(int i = 0; i < K; i++) {
			int num = sc.nextInt();
			int dir = sc.nextInt();
			rotate(q, num - 1, dir);
			for(int j = 0; j < visited.length; visited[j++] = false);
		}
		int sum = 0;
		for(int i = 0, point = 1; i < 4; i++, point *= 2) {
			if(q.get(i).get(0) == 1) sum += point;
		}
		System.out.println(sum);
	}
}

그러니까 기존엔 스위치문이 원래 visited[now] = true 위에 있었다 ㅋㅋㅋ

스위치문 위치만 바꿔주었다!