[ Algorithm ] 백준 톱니바퀴 (14891번)
오늘 풀이 할 문제는 백준 톱니바퀴 문제이다. 최근에 계속 삼성 SW 역량 테스트 기출 문제 문제집에 있는 문제들을 풀어보고 있는데 문제들이 왜 전부 굴리고 회전하는걸 좋아하는지 모르겠다. 아무튼 이 문제도 톱니바퀴를 회전해서 푸는 문제인데 톱니바퀴를 회전하는 부분만 잘 짜면 다른 부분은 크게 어렵지 않은 문제이다.
문제
문제는 여기에 참조한다.
풀이
우선 4개의 톱니바퀴를 생성하고 관리하기 위해 클래스로 정의했는데 사실 필드가 int형 1차원 배열 하나라서 그냥 배열로만 풀어도 똑같이 풀릴 것 같다. 필자는 회전을 인덱스를 조정해서 구현 했는데 질문 게시판에 다른 풀이를 보니 LinkedList를 써서 앞에 있는 톱니를 빼서 뒤로 넣는, 혹은 그 반대로 해서 회전을 구현한 풀이도 있었다. 가독성을 보면 LinkedList를 쓰는 편이 더 좋을 것 같다는 생각을 했다.
private static void turn(Gear gear, int dir) {
int[] newStatus = new int[8];
// 톱니바퀴를 시계 방향으로 회전하는 경우
if(dir == 1) {
for(int i = 0; i < 8; i++) {
newStatus[i] = gear.status[(i+7)%8];
}
}
// 톱니바퀴를 반시계 방향으로 회전하는 경우
else if(dir == -1) {
for(int i = 0; i < 8; i++) {
newStatus[i] = gear.status[(i+1)%8];
}
}
// 톱니바퀴의 상태를 회전한 결과로 변경
for(int i = 0; i < 8; i++) {
gear.status[i] = newStatus[i];
}
}
private static class Gear {
private int[] status;
Gear(int[] status) {
this.status = status;
}
}
turn 메소드에 회전시킬 톱니바퀴와 방향을 넣으면 해당 방향으로 회전하도록 구현했는데 톱니바퀴의 톱니가 0번부터 7번까지 있다고 할 때 시계 방향으로 회전하면 1번 위치에 0번 톱니, 2번 위치에 1번 톱니, … 이런식으로 와야 할 것이다. 반대로 회전시키는 경우는 1번 위치에 2번 톱니, 2번 위치에 3번 톱니, … 이런식으로 와야 할 것이다. (i+7)%8 계산식으로 시계 방향 회전을 구현하고 (i+1)%8 계산식으로 반시계 방향 회전을 구현했다. 그리고 마지막에 원래 톱니바퀴 상태를 회전시킨 상태로 업데이트 한다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
gears = new ArrayList<>();
gears.add(new Gear(null));
for(int i = 1; i <= 4; i++) {
int[] status = new int[8];
String line = br.readLine();
for(int j = 0; j < 8; j++) {
status[j] = Character.getNumericValue(line.charAt(j));
}
gears.add(new Gear(status));
}
main 메소드 안에서는 톱니바퀴를 저장할 리스트를 생성하고 톱니바퀴의 상태를 입력받아 톱니를 생성하고 리스트에 저장했다. 나중에 리스트를 조회할 때 톱니바퀴의 번호 그대로 조회하기 위해 더미값을 하나 추가했다.
이제 k번의 회전 방법을 입력 받아 회전하면 된다.
int k = Integer.parseInt(br.readLine());
for(int i = 0; i < k; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// 회전시킬 모든 톱니바퀴의 번호와 방향을 저장
List<Change> list = new ArrayList<>();
// 처음 회전시킬 톱니바퀴의 번호와 방향
int num = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
list.add(new Change(num, dir));
// 처음 톱니바퀴의 왼쪽 톱니바퀴를 확인
int currDir = dir;
for(int j = num-1; j >= 1; j--) {
if(gears.get(j+1).status[6] != gears.get(j).status[2]) {
list.add(new Change(j, currDir*-1));
currDir *= -1;
}
else break;
}
// 처음 톱니바퀴의 오른쪽 톱니바퀴를 확인
currDir = dir;
for(int j = num+1; j <= 4; j++) {
if(gears.get(j-1).status[2] != gears.get(j).status[6]) {
list.add(new Change(j, currDir*-1));
currDir *= -1;
}
else break;
}
// 모든 톱니바퀴 회전시키기
for(Change change : list) {
turn(gears.get(change.num), change.dir);
}
}
private static class Change {
private int num;
private int dir;
Change(int num, int dir) {
this.num = num;
this.dir = dir;
}
}
톱니바퀴를 회전시킬 때 주의해야 할 점은 한 개의 톱니바퀴를 회전시킬 때, 영향을 받는 다른 톱니바퀴들 또한 동시에 움직인다는 것이다. 그래서 톱니바퀴를 회전시키고 상태를 업데이트 하는 과정은 처음 톱니바퀴의 회전으로 인해 영향을 받는 다른 톱니바퀴들을 따로 모아놓은 후 한 번에 처리해야 한다. 그렇게 하기 위해 Change 클래스를 생성했고 회전 시킬 톱니바퀴의 번호와 회전 방향을 묶어서 함께 저장했다. 처음 톱니바퀴를 기준으로 왼쪽, 오른쪽에 있는 톱니바퀴들을 확인하면서 영향을 받는 톱니바퀴들을 리스트에 저장하고 마지막에 한번에 회전 시킨다.
k번의 회전을 마치고 나면 점수를 출력하면 된다.
int score = 0;
for(int i = 1; i <= 4; i++) {
Gear gear = gears.get(i);
if(i == 1) {
if(gear.status[0] == 0) score += 0;
else score += 1;
}
else if(i == 2) {
if(gear.status[0] == 0) score += 0;
else score += 2;
}
else if(i == 3) {
if(gear.status[0] == 0) score += 0;
else score += 4;
}
else {
if(gear.status[0] == 0) score += 0;
else score += 8;
}
}
System.out.println(score);
마지막으로 전체 코드이다.
import java.io.*;
import java.util.*;
public class Main {
static List<Gear> gears;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
gears = new ArrayList<>();
gears.add(new Gear(null));
for(int i = 1; i <= 4; i++) {
int[] status = new int[8];
String line = br.readLine();
for(int j = 0; j < 8; j++) {
status[j] = Character.getNumericValue(line.charAt(j));
}
gears.add(new Gear(status));
}
int k = Integer.parseInt(br.readLine());
for(int i = 0; i < k; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// 회전시킬 모든 톱니바퀴의 번호와 방향을 저장
List<Change> list = new ArrayList<>();
// 처음 회전시킬 톱니바퀴의 번호와 방향
int num = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
list.add(new Change(num, dir));
// 처음 톱니바퀴의 왼쪽 톱니바퀴를 확인
int currDir = dir;
for(int j = num-1; j >= 1; j--) {
if(gears.get(j+1).status[6] != gears.get(j).status[2]) {
list.add(new Change(j, currDir*-1));
currDir *= -1;
}
else break;
}
// 처음 톱니바퀴의 오른쪽 톱니바퀴를 확인
currDir = dir;
for(int j = num+1; j <= 4; j++) {
if(gears.get(j-1).status[2] != gears.get(j).status[6]) {
list.add(new Change(j, currDir*-1));
currDir *= -1;
}
else break;
}
// 모든 톱니바퀴 회전시키기
for(Change change : list) {
turn(gears.get(change.num), change.dir);
}
}
int score = 0;
for(int i = 1; i <= 4; i++) {
Gear gear = gears.get(i);
if(i == 1) {
if(gear.status[0] == 0) score += 0;
else score += 1;
}
else if(i == 2) {
if(gear.status[0] == 0) score += 0;
else score += 2;
}
else if(i == 3) {
if(gear.status[0] == 0) score += 0;
else score += 4;
}
else {
if(gear.status[0] == 0) score += 0;
else score += 8;
}
}
System.out.println(score);
}
private static void turn(Gear gear, int dir) {
int[] newStatus = new int[8];
// 톱니바퀴를 시계 방향으로 회전하는 경우
if(dir == 1) {
for(int i = 0; i < 8; i++) {
newStatus[i] = gear.status[(i+7)%8];
}
}
// 톱니바퀴를 반시계 방향으로 회전하는 경우
else if(dir == -1) {
for(int i = 0; i < 8; i++) {
newStatus[i] = gear.status[(i+1)%8];
}
}
// 톱니바퀴의 상태를 회전한 결과로 변경
for(int i = 0; i < 8; i++) {
gear.status[i] = newStatus[i];
}
}
private static class Gear {
private int[] status;
Gear(int[] status) {
this.status = status;
}
}
private static class Change {
private int num;
private int dir;
Change(int num, int dir) {
this.num = num;
this.dir = dir;
}
}
}
사실 turn 메소드를 구현할 때 시계 방향과 반시계 방향의 인덱스 계산식을 반대로 써서 찾는데 좀 오래 걸렸다. 다시 말하지만 이번 문제는 LinkedList를 쓰는 편이 더 직관적이고 가독성이 좋다. 스스로를 위해서라도 더 직관적인 코드를 쓰도록 노력 해야겠다.