[BOJ_15662] 톱니바퀴 ( java)

문제링크

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

15662번: 톱니바퀴 (2)

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 객체 구현

톱니바퀴라는 객체를 구현하여 문제를 해결할 수 있습니다. 톱니바퀴 객체의 동작은 왼쪽 혹은 오른쪽으로 굴러가는 것입니다. 그리고 추가적으로 왼쪽 톱니바퀴와 만나는 지점의 톱니의 값과 오른쪽 톱니바퀴와 만나는 지점의 톱니의 값 그리고 맨 위 지점의 톱니가 N인지 S인지 알려줄 수 있습니다.

 

톱니를 돌리는 방법은 index를 변경해주면됩니다. 배열에서 %연산자를 활용하여 배열의 인덱스의 첫점과 끝점을 이어주고, 만약 오른쪽으로 돌리는 경우 배열의 참조하는 인덱스를 1만 작게, 왼쪽으로 움직일 경우 1만 크게 구현해주면 됩니다.(코드참고)

 

위의 설명대로 톱니바퀴를 구현하였다면, 문제 조건에 맞추어 톱니바퀴를 돌려주어야합니다. 이때 돌아갈때, 만나고 있는 톱니의 극성에 따라서 돌아갈지 안돌아갈지가 결정됩니다.

출처 - https://www.acmicpc.net/problem/15662

만약, 왼쪽 1번과 2번 톱니처럼 N과 S로 반대극이 만나 있다면 둘 중 하나의 톱니바퀴가 돌아갈 때 함께 돌아가고, 3번과 4번의 톱니바퀴처럼 같은 극이 맞닿아 있다면 돌아가지 않습니다.  따라서 위 예시에서 3번 톱니바퀴가 돌아간다고 하면, 4번 톱니바퀴는 그대로 있고, 3번으로인해 2번이 돌아가고 2번으로인해 1번이 돌아가게 됩니다. 이 때 돌아가는 방향은 돌아가게 만든 원인의 톱니가 도는 방향의 반대로 돌면 됩니다.

구현코드

package backjoon_15662;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int sawLength = 8;
        int n = sc.nextInt();
        Gear[] gears = new Gear[n];

        for(int i = 0; i < n; i++){
            int[] sawTooth = new int[sawLength];
            String line = sc.next();
            for(int j = 0; j < sawLength; j++){
                sawTooth[j] = line.charAt(j) - '0';
            }
            gears[i] = new Gear(sawTooth);
        }

        int moveCount = sc.nextInt();
        while (moveCount-- > 0){
            int gearNum = sc.nextInt();
            int movement = sc.nextInt();
            IterMovement(gearNum-1,movement,gears);
        }

        int count = 0;
        for(int i = 0; i < n; i++){
            if(gears[i].getTwelveSawTooth() == 1)
                count++;
        }
        System.out.println(count);
    }

    public static void IterMovement(int gearNum,int movement, Gear[] gears){
        int left = gears[gearNum].getLeftSawTooth();
        int right = gears[gearNum].getRightSawTooth();
        movement(gearNum, movement, gears);

        int move = movement;
        for(int i = gearNum-1; i >= 0; i--){
            int getLeftSawTooth = gears[i].getRightSawTooth();
            if(left != getLeftSawTooth){
                left = gears[i].getLeftSawTooth();
                movement(i, move*=-1, gears);
            }
            else{
                break;
            }
        }

        move = movement;
        for(int i = gearNum+1; i < gears.length; i++){
            int getRightSawTooth = gears[i].getLeftSawTooth();
            if(right != getRightSawTooth){
                right = gears[i].getRightSawTooth();
                movement(i, move*=-1, gears);
            }
            else{
                break;
            }
        }
    }

    private static void movement(int gearNum, int movement, Gear[] gears) {
        if (movement == 1) {
            gears[gearNum].moveRight();
        } else {
            gears[gearNum].moveLeft();
        }
    }


    public static class Gear{
        private int[] sawTooth;
        private int sawLength;
        private int startIndex;

        public Gear(int[] sawTooth){
            startIndex = 6;
            this.sawTooth = sawTooth;
            sawLength = 8;
        }

        public int getLeftSawTooth(){
            return sawTooth[startIndex];
        }

        public int getRightSawTooth(){
            return sawTooth[(startIndex+sawLength/2)%sawLength];
        }

        public int getTwelveSawTooth(){
            return sawTooth[(startIndex+sawLength/4)%sawLength];
        }

        public void moveLeft(){
            startIndex +=1;
            startIndex %= sawLength;
        }
        public void moveRight(){
            startIndex += sawLength-1;
            startIndex %= sawLength;
        }
    }
}

 

시간복잡도

톱니 하나를 돌리는데 걸리는 시간은 상수 $O(1)$입니다. 한번 회전할 때마다 최악의 경우 모든 톱니가 돌릴 수 있기 때문에 $O(N)$이 걸릴 수 있고, 총 K번 회전하기 때문에 시간복잡도는 $O(K*N)$이 됩니다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)