• 백준 14891번 톱니바퀴 :: 마이구미
    알고리즘 풀이/스택, 큐 2018. 4. 1. 21:46
    반응형

    이 글은 백준 알고리즘 문제 14891번 "톱니바퀴" 를 풀이한다.

    2017 삼성 SW 역량 테스트 기출 문제이다.

    시뮬레이션을 통한 하드코딩으로 풀 수도 있다.

    본인의 접근 방법은 덱(dequeue) 과 같은 개념과 재귀를 활용해 문제를 해결한다.

    문제 링크 - https://www.acmicpc.net/problem/14891


    총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.


    톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.


    다소 문제의 설명에서 많은 그림과 많은 글들이 있어, 복잡해보인다.

    문제는 그렇게 복잡하지 않고, 이해하기도 어렵지 않다.

    하지만 본인은 문제를 잘못 이해해서 꽤 오래 걸렸다.


    문제를 통해 알 수 있는 정보는 다음과 같다.


    1. 톱니바퀴는 총 4개가 존재한다.
    2. 각 톱니바퀴의 톱니는 총 8개가 존재한다.
    3. 서로 맞닿은 극의 톱니는 2번과 6번이다.
    4. 서로 맞닿은 극이 다르면 회전시키고 그렇지 않다면, 그대로 유지한다.
    5. 톱니바퀴의 인접한 톱니바퀴의 인접한 톱니바퀴도 고려해야한다.
    6. 하나의 톱니바퀴를 기준으로 인접한 톱니바퀴는 기준 톱니바퀴의 반대방향으로 회전하게 된다.
    7. 입력을 통해 첫 회전 시키는 톱니바퀴는 무조건 회전하는 것이고, 인접한 톱니바퀴가 회전여부를 판단하는 것이다.


    본인은 양쪽 모두 맞닿은 극이 같을 경우, 그대로 유지해버렸다.

    즉, 6번을 이해하지 못해 오래 걸렸다.

    다시 말하자면, 주어지는 입력(회전하는 톱니바퀴 번호) 에 대한 톱니바퀴는 무조건 회전한다.


    5번의 경우는 톱니바퀴들은 체인처럼 연결된다고 볼 수 있다.

    즉, 4, 3, 2, 1 번 톱니바퀴 모두 회전할 수 있다.

    4, 3, 2 번 톱니바퀴만 회전할 수 있다.

    4, 3 번 톱니바퀴만 회전할 수 있다.

    4 번 톱니바퀴만 회전할 수 있다.


    결론적으로 문제를 통해 얻을 수 있는 정보를 가지고 시뮬레이션을 통해 그대로 구현하면 된다.

    구현에 있어, 재귀와 덱을 사용하면 깔끔한 코드를 작성할 수 있다.

    인접한 톱니바퀴는 계속 이어질 수도 있기 때문에 왼쪽과 오른쪽을 나누어 재귀적으로 해결한다.

    회전은 반시계 방향일 경우 맨 앞의 요소를 맨 뒤로 보내면 되고, 시계 방향일 경우 맨 뒤의 요소를 맨 앞으로 보내면 된다.

    이와 같은 개념은 덱을 나타낼 수 있다.


    14891번 톱니바퀴


    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/dequeue/14891.java


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    static LinkedList<Integer>[] list = (LinkedList<Integer>[]) new LinkedList[5];
     
    private void solve() {
        for (int i = 1; i <= 4; i++) {
            list[i] = new LinkedList<Integer>();
            String input = sc.readLine();
            for (String s : input.split("")) {
                int n = Integer.parseInt(s);
                list[i].add(n);
            }
        }
     
        int k = sc.nextInt();
        while (k-- > 0) {
            int n = sc.nextInt();
            int d = sc.nextInt();
     
            left(n - 1-d);
            right(n + 1-d);
            rotate(n, d);
        }
     
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            if (list[i + 1].get(0== 1) {
                ans += (int) Math.pow(2, i);
            }
        }
        System.out.println(ans);
    }
     
    public static boolean check(int a, int b) {
        if (a > b) {
            // left
            if (list[a].get(6== list[b].get(2)) {
                return false;
            } else {
                return true;
            }
        } else {
            if (list[a].get(2== list[b].get(6)) {
                return false;
            } else {
                return true;
            }
        }
    }
     
    public static void rotate(int n, int direction) {
        if (direction == 1) {
            list[n].addFirst(list[n].pollLast());
        } else {
            list[n].addLast(list[n].pollFirst());
        }
    }
     
    public static void left(int n, int direction) {
        if (!(<= n && n <= 4))
            return;
     
        if (check(n, n + 1)) {
            left(n - 1-direction);
            rotate(n, direction);
        }
    }
     
    public static void right(int n, int direction) {
        if (!(<= n && n <= 4))
            return;
     
        if (check(n, n - 1)) {
            right(n + 1-direction);
            rotate(n, direction);
        }
    }
    cs


    반응형

    댓글 3

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.09.17 23:38 신고

      단데기 - 덕분에 공부잘하고있습니다 항상 감사하네요^^7
      회전은 시계 방향일 경우 맨 앞의 요소를 맨 뒤로 보내면 되고, 반시계 방향일 경우 맨 뒤의 요소를 맨 앞으로 보내면 된다.
      이와 같은 개념은 덱을 나타낼 수 있다
      이부분에 혹시 반대로 설명하는게 맞는게 아닌가해서요 시계방향일때 맨뒤껄 맨앞으로 반시계일때 맨앞껄 맨뒤로 아닌가 합니다 ㅎㅎㅎ
      =>
      말씀하신 부분이 맞습니다!
      제가 반대로 했군요..
      수정하였습니다 감사합니다~

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.09.17 23:39 신고

      B Double - 마이구미님 덕분에 SW 테스트에 도움이 되네요
      => 도움이 되셨다니 감사합니다~

    • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.09.17 23:39 신고

      Ko William DJ - 마이구미님 궁금한게 있는데용
      문제 이해가 완전히 안된 것일 수도 있는데.. 제 생각에는 현재 톱니바퀴가 먼저 rotate한 후에 상태를 가지고 왼쪽 오른쪽 톱니를 비교해서 넘겨야할 것 같은데
      로테이트를 나중에 한 이유가 있나용?
      =>
      회전여부가 무조건 true 인 경우가 아니기 때문입니다.
      회전여부를 판단하여 회전할지말지 결정해야하는데... 어떤 질문인지 확실히 이해하지 못했습니다!
      혹시 접근 방법이 다르게 하셔서 푸셨다면 그것 또한 맞는 방법이겠지요!
      저의 접근이 100% 정답은 아니니깐유!

Designed by Tistory.