[BOJ 14891 / C++] 톱니바퀴 (시뮬레이션)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

vector<char> cw(vector<char>& wheel) {
    vector<char> tmp(8, 0);
    tmp[0] = wheel[7];
    for (int i = 1; i < 8; i++) {
        tmp[i] = wheel[i-1];
    }
    return tmp;
}

vector<char> ccw(vector<char>& wheel) {
    vector<char> tmp(8, 0);
    tmp[7] = wheel[0];
    for (int i = 0; i < 7; i++) {
        tmp[i] = wheel[i+1];
    }
    return tmp;
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    vector<vector<char>> wheel(4, vector<char>(8, 0));
    for (int i = 0; i < 4; i++) {
        string inp;
        cin >> inp;
        for (int j = 0; j < 8; j++) {
            wheel[i][j] = inp[j];
        }
    }

    int k;
    cin >> k;
    while (k--) {
        int idx, dir;
        cin >> idx >> dir;
        idx -= 1;

        vector<int> dirList(4, 0);
        dirList[idx] = dir;
        
        // 오른쪽 기어들 회전 방향 설정
        int curDir = dir;
        for (int i = idx+1; i < 4; i++) {
            if (wheel[i][6] == wheel[i-1][2]) break;
            else {
                if (curDir == 1) {
                    dirList[i] = -1;
                    curDir = -1;
                }
                else if (curDir == -1) {
                    dirList[i] = 1;
                    curDir = 1;
                }
            } 
        }

        // 왼쪽 기어들 회전 방향 설정
        curDir = dir;
        for (int i = idx-1; i >= 0; i--) {
            if (wheel[i+1][6] == wheel[i][2]) break;
            else {
                if (curDir == 1) {
                    dirList[i] = -1;
                    curDir = -1;
                }
                else if (curDir == -1) {
                    dirList[i] = 1;
                    curDir = 1;
                }
            } 
        }

        // 방향대로 전체 회전
        for (int i = 0; i < 4; i++) {
            if (dirList[i] == 0) continue;
            else if (dirList[i] == 1) { // 시계방향
                wheel[i] = cw(wheel[i]);
            }
            else if (dirList[i] == -1) { // 반시계방향
                wheel[i] = ccw(wheel[i]);
            }
        }
    }

    int score = 0;
    for (int i = 0; i < 4; i++) {
        if (wheel[i][0] == '1') {
            score += (1 << i);
        }
    }
    cout << score;
}

 

 

2. 시간복잡도

회전횟수 k = 100이고, 회전방향 설정에는 4번, 전체 회전에는 O(n) n=8 정도이므로 시간제한 2초안에는 충분히 통과 가능하다.

 

 

3. 분석

충실히 구현해주면 된다. gpt를 통해 다른 방법들이 있어 남겨놓는다.

 

(1) 컨테이너 선택

• vector<char>로 충분히 빠르고, 크기도 고정되어 있어서 문제 없지만
• deque<char>를 쓰면 앞/뒤 삽입·삭제(push_front/push_back)가 좀 더 직관적이기도 해.

deque<char> gear(8);
// 시계 회전: 
gear.push_front(gear.back());
gear.pop_back();
// 반시계 회전:
gear.push_back(gear.front());
gear.pop_front();

 

한칸씩만 움직이므로 deque을 쓰는 것도 타당해 보인다.

 

 

(2) std::rotate 활용

• <algorithm> 헤더의 std::rotate를 쓰면 cw/ccw 함수 없이도 한 줄로 회전 가능해.

// 시계 회전
rotate(wheel.begin(), wheel.end()-1, wheel.end());
// 반시계 회전
rotate(wheel.begin(), wheel.begin()+1, wheel.end());

 

• [first, last) 구간을 left-rotate 한다고 생각하면 돼.
• middle 이터레이터 위치의 요소가 제일 앞으로 오고,
• 그 앞에 있던 [first, middle) 구간이 뒤로 붙는다.

rotate를 활용하면 함수를 따로 구현하지 않고 한줄로 처리할 수 있어 편하다.