[python] 백준 14891 - 톱니바퀴

출처 : 백준, https://www.acmicpc.net/problem/14891 

14891번: 톱니바퀴

 

 

먼저, 생각해야 할 부분

 

1. 보자마자 가장 쉬운 접근법이 떠올랐을텐데 그 풀이 방법이 통과 가능한지 검토해보자.

    불가능하다는 말이 아니다.

2. 구현 문제는 놓치는 부분 없이 꼼꼼하게 풀어야한다.

    조건을 놓치지 않게 조건을 잘 명시하는 의사코드를 대략적으로 적어보자

---

 

풀이 : Multiple Pointer

 

import sys

def solution(gears, rot_count, rot_way):
  # 서로 마주 보는 극이 다르면 상대 기어는 반대 방향으로 회전
  # 서로 마주 보는 극이 같다면 상대 기어는 회전하지 않음

  # 12시 방향이 N극이면 0, S극이면 1의 합을 2**번째와 곱해서 return

  pointer = [0, 0, 0, 0]
  
  # 시계방향으로 돌리면 p를 -1
  # 반시계방향으로 돌리면 p를 +1

  for nth, dir in rot_way:
    #모든 기어의 pointer 기준으로 +2번과 +6번을 뽑는다
    nth -= 1
    dir *= -1

    right_gear = []
    left_gear = []

    for i in range(4):
      right_target_pointer = pointer[i] + 2 if pointer[i] + 2 < 8 else (pointer[i] + 2) % 8
      left_target_pointer = pointer[i] + 6 if pointer[i] + 6 < 8 else (pointer[i] + 6) % 8
      
      right_gear.append(gears[i][right_target_pointer])
      left_gear.append(gears[i][left_target_pointer])

    pointer[nth] += dir

    # dir의 방향을 톱니마다 바꿔줌
    temp_dir = dir

    # nth를 기준으로 오른쪽으로 가는 아이들은 왼6과 오2를 비교
    for i in range(nth, 3):
      if right_gear[i] != left_gear[i+1]: #둘이 다른 극이라면
        pointer[i+1] -= temp_dir
        temp_dir *= -1
      else:
        break

    temp_dir = dir

    # 왼쪽으로 가는 아이들은 왼2와 오6을 비교
    for i in range(nth, 0, -1):
      if left_gear[i] != right_gear[i-1]:
        pointer[i-1] -= temp_dir
        temp_dir *= -1
      else:
        break

    # pointer 순환처리
    for i in range(4):
      if pointer[i] < 0:
        pointer[i] = 7

      if pointer[i] > 7:
        pointer[i] = 0

  return sum([gears[i][pointer[i]] * (2 ** i) for i in range(4)])

def input():
  return sys.stdin.readline().rstrip()
  
gears = [list(map(int, list(input()))) for _ in range(4)]

rot_count = int(input())
rot_way = [list(map(int, input().split())) for _ in range(rot_count)]

answer = solution(gears, rot_count, rot_way)

print(answer)

 

처음에는 Multiple Pointer로 풀면 좋겠다 생각해서 풀었는데,

풀고 보니까 굳이 Multiple Pointer로 풀 정도로 시간이 많이 걸리는 문제가 아니었다.

 

풀이2 : pop Array

 

def rotateGear(gear, dir):
    CLOCKWISE = 1
    COUNTER_CLOCKWISE = -1

    if dir == CLOCKWISE:
        element = gear.pop()
        gear.insert(0, element)
        return gear
    else:
        new_gear = gear[1:]
        new_gear.append(gear[0])
        return new_gear
        
def solution(gears, rot_way):
    #rot_way에서 돌리면서 좌/우로 for문 돌림

    for gear_idx, dir in rot_way:
        gear_idx -= 1

        # 처음에 배열에서 2, 6을 다 뽑음
        left_pole = []  # 6번쨰
        right_pole = []  # 2번쨰

        for g in gears:
            left_pole.append(g[6])
            right_pole.append(g[2])

        gears[gear_idx] = rotateGear(gears[gear_idx], dir)

        temp_dir = dir

        for i in range(gear_idx, 3):
            if right_pole[i] != left_pole[i+1]:
                temp_dir *= -1
                gears[i + 1] = rotateGear(gears[i + 1], temp_dir)
            else:
                break

        temp_dir = dir

        for i in range(gear_idx, 0, -1):
            if left_pole[i] != right_pole[i - 1]:
                temp_dir *= -1
                gears[i - 1] = rotateGear(gears[i - 1], temp_dir)
            else:
                break

    return sum([gears[i][0] * (2 ** i) for i in range(4)])

gears = [list(map(int, list(input()))) for _ in range(4)]

rot_count = int(input())
rot_way = [list(map(int, input().split())) for _ in range(rot_count)]

answer = solution(gears, rot_way)

print(answer)

 

하나의 기어당 7개의 성분이 있고, 회전은 총 100번 발생하기 때문에

최악의 경우가 100번 중 매번마다 최대 7개의 성분이 4개의 모든 기어에서 발생하는 경우이다.

이 경우 100 * 7 * 4 = 2800번의 연산이 필요한데 생각보다 무리가 가지 않는다.

회전 횟수 k가 엄청나게 큰 숫자라면 모르겠지만,

기어의 개수와 성분 개수 모두 4, 7로 고정되어있는 상태라서 array를 직접 빼고 넣고 해도 통과할 수 있는 풀이가 된다.

 

---

 

알게 된 점

 

가장 쉬운 방법으로 풀었을 경우 시간 복잡도를 통과할 수 있을지 입력의 범위를 살펴보고 결정해야한다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들