1. 문제요약
- 4개의 톱니바퀴가 왼쪽부터 1,2,3,4 의 번호를 가짐.
- 12시방향부터 시계방향으로의 각 톱니의 상태가 주어짐(N : 0, S : 1)
- N번째 바퀴를 K번의 바퀴 회전시킴. (시계 : 1, 반시계 : -1)
3.1 해당 N번째 바퀴와 맞닿는 N-1, N+1 바퀴의 극이 같다면, pass
3.2 해당 N번째 바퀴와 맞닿는 N-1, N+1 바퀴의 극이 다르면, 양측 바퀴는 역방향으로 돎 - 모두 회전 후, 4개의 바퀴의 12시 방향 극에 따라 점수 차등분배. 해당 점수 출력
2. 알고리즘
톱니바퀴 : 0 1 2 3 4 5 6 7
시계방향 : 7 0 1 2 3 4 5 6
반시계방향 : 1 2 3 4 5 6 7 0
- linkedList로 톱니 회전 후 상태 보관
- N번째 바퀴에서 3.2 조건 만족 시 재귀로 톱니 회전 시기기
- 필요 인자 : 우/좌(반대 방향 재귀 안가게), 회전해야할 방향, 현재 톱니 위치
- 다른 바퀴와 닿는 2, 6번의 인덱스에 해당하는 값 보고 다음 바퀴의 회전/비회전 재귀 호출
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static LinkedList<Integer>[] topni;
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
topni = new LinkedList[5];
for(int i=0; i<5; i++) {
topni[i] = new LinkedList<>();
}
for(int i=1; i<=4; i++) {
String s = br.readLine();
for(int j=0; j<8; j++){
char c = s.charAt(j);
topni[i].add(Integer.parseInt(String.valueOf(c)));
}
}
int K = Integer.parseInt(br.readLine());
while (K --> 0) {
st = new StringTokenizer(br.readLine());
int topniIdx = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
tossRightTopni(dir, topniIdx);
tossLeftTopni(dir, topniIdx);
spinTopni(dir, topniIdx);
}
int answer = 0;
int score = 1;
for(int i=1; i<=4; i++){
if(topni[i].get(0)==1) answer+=score;
score *=2;
}
System.out.println(answer);
}
/*
톱니바퀴 : 0 1 2 3 4 5 6 7
시계방향(1) : 7 0 1 2 3 4 5 6
반시계방향(-1) : 1 2 3 4 5 6 7 0
*/
static void spinTopni(int dir, int topniIdx) {
if(dir==1) {
Integer last = topni[topniIdx].pollLast();
topni[topniIdx].addFirst(last);
} else {
Integer first = topni[topniIdx].pollFirst();
topni[topniIdx].addLast(first);
}
}
static boolean tossRightTopni(int dir, int topniIdx) {
int reverseDir = dir == 1 ? -1 : 1;
boolean end = false;
//오른쪽
int exTonpniIdx = topniIdx;
int rightTopniIdx = topniIdx+1;
while (checkArragne(rightTopniIdx)&&!end) {
if(topni[exTonpniIdx].get(2)!=topni[rightTopniIdx].get(6)) {
end = tossRightTopni(reverseDir, rightTopniIdx);
} else break;
exTonpniIdx = rightTopniIdx;
rightTopniIdx++;
}
if(checkArragne(topniIdx+1)&&end) spinTopni(reverseDir, topniIdx+1);
return true;
}
static boolean tossLeftTopni(int dir, int topniIdx) {
int reverseDir = dir == 1 ? -1 : 1;
boolean end = false;
//왼쪽
int exTonpniIdx = topniIdx;
int leftTonniIdx = topniIdx-1;
while (checkArragne(leftTonniIdx)&&!end) {
if(topni[exTonpniIdx].get(6)!=topni[leftTonniIdx].get(2)) {
end = tossLeftTopni(reverseDir, leftTonniIdx);
} else break;
exTonpniIdx = leftTonniIdx;
leftTonniIdx--;
}
if(checkArragne(topniIdx-1)&&end)spinTopni(reverseDir, topniIdx-1);
return true;
}
static boolean checkArragne(int idx){
if(idx < 1 || idx > 4) return false;
return true;
}
}
처음 이 문제를 보자마자, 톱니가 회전하는 조건을 양 옆으로 펴져나가야 한다고 생각해서 재귀함수를 이용하기로 했었다.
나는 양옆으로 돌아야 하는 톱니까지 재귀함수를 통해 간 다음, 재귀함수를 빠져나오기 전 현재 톱니를 회전시키는 방법을 선택했다.
그러나.. 생각보다 재귀함수에 대해 조건이 너무 많이 생겼고, 특히 end 라는 불리언 변수까지 어거지로 사용하다 보니 코드가 많이 더럽다고 느꼈다.
근데??????????????????? 다른 사람들의 코드가 너무 깔끔하게 내 코드 개선을 시켜줬다.
4. 알고리즘2
첫 톱니바퀴를 기준으로 양옆으로 뻗어나간다는 개념은 동일하다. 그러나 굳이 재귀함수를 이용하는게 아닌, 배열을 하나 만들어 해당 인덱스의 톱니의 회전방향만 기록해주면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static LinkedList<Integer>[] topni;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
topni = new LinkedList[5];
for (int i = 0; i < 5; i++) {
topni[i] = new LinkedList<>();
}
// 톱니바퀴 입력
for (int i = 1; i <= 4; i++) {
String s = br.readLine();
for (int j = 0; j < 8; j++) {
char c = s.charAt(j);
topni[i].add(Integer.parseInt(String.valueOf(c)));
}
}
int K = Integer.parseInt(br.readLine());
StringTokenizer st;
while (K-- > 0) {
st = new StringTokenizer(br.readLine());
int topniIdx = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
int[] rotate = new int[5];
rotate[topniIdx] = dir;
// 왼쪽 전파
for (int i = topniIdx; i > 1; i--) {
if (topni[i].get(6) != topni[i - 1].get(2)) {
rotate[i - 1] = -rotate[i];
} else {
break;
}
}
// 오른쪽 전파
for (int i = topniIdx; i < 4; i++) {
if (topni[i].get(2) != topni[i + 1].get(6)) {
rotate[i + 1] = -rotate[i];
} else {
break;
}
}
// 실제 회전 적용
for (int i = 1; i <= 4; i++) {
if (rotate[i] != 0) {
spinTopni(rotate[i], i);
}
}
}
// 점수 계산
int answer = 0;
int score = 1;
for (int i = 1; i <= 4; i++) {
if (topni[i].get(0) == 1) {
answer += score;
}
score *= 2;
}
System.out.println(answer);
}
/*
톱니바퀴 인덱스
0 1 2 3 4 5 6 7
시계방향(1) : 7 0 1 2 3 4 5 6
반시계방향(-1) : 1 2 3 4 5 6 7 0
*/
static void spinTopni(int dir, int topniIdx) {
if (dir == 1) {
Integer last = topni[topniIdx].pollLast();
topni[topniIdx].addFirst(last);
} else {
Integer first = topni[topniIdx].pollFirst();
topni[topniIdx].addLast(first);
}
}
}
첫 번째 시도가 개선 전, 두 번째 시도가 개선 후이다.
시간상 큰 차이가 없긴 한데, 그건 톱니가 4개뿐이라 재귀함수를 많이 거치지 않아서 그렇다.
나중에 돌아야 할 톱니가 많아진다면, 당연히 나의 방법이 느릴 것이다. 코드 역시 더 복잡하기에 개선 후의 코드가 더 좋은 것 같다!
