백준 14891 톱니바퀴

문제가 너무 길어서 짤렸다..

 

처음 문제만 읽어 보고 나서 쉬운 문제라고 생각했다. 1시간 안에 끝날 줄 알았는데 2시간 걸렸다..

너무 안일하게 생각하고, 구체적으로 어떤 프로세스로 돌아가는지 생각하지 않고 코딩하기 시작했다.

앞에서도 같은 실수를 여러번 반복했기 때문에 구체적으로 생각하고 들어가려고 조심하고 있었고, 이번에도 구체적으로 생각했다고 생각했는데, 사실은 구체적이지 않았던 것 같다.

 

계속 뭐가 잘못됐는지 찾다가 톱니바퀴가 아니라 내가 돌아버리는 것 같았다.(뇌도 돌아버리는 것 같았다.)

계속 알고리즘 문제를 풀다보니 반복하는 부분을 함수로 계속 만들고, 코드도 처음에 비해서 조금씩 군더더기를 걷어내고 있는 중인 것 같긴하다. 하지만 여전히 아쉽고 매우 매우 매우 매우 많이 부족하다.

 

1. 예전 같으면 N극과 S극이 다르거나 같은 경우를 if문 여러개로 나눴을 텐데, 두 원소를 더하면 1이 될 때라는 조건 하나만으로 처리했다. 그리고 답을 출력할 때 예전 같았으면 더하는데 또 잡다한 코드로 여러 줄을 할애했을 텐데, 이번에는 한 줄에 보기 쉽게 하려고 했다. 또한, 회전 방향을 저장할 때 예전 같았으면 if문으로 1이 아니면 -1을 넣는 식으로 했을 텐데, 이번에는 -1 * dir 이런식으로 넘겨주었다. 이러한 방법들을 계속해서 숙련해 나가야 겠다. 이런 것들이 경험치인 것 같다. 빨리 레벨업하고 싶다...

 

2. 하지만 톱니바퀴가 어떤 조건에서 돌아야 하고 돌지 말아야 하는지를 제대로 체크하지 않고, 코딩을 시작한 것이 화근이었다. 뭔가 연속적으로 톱니바퀴가 돌아간다는 생각은 했지만, 이를 코드로 어떻게 구현해야 할 지 감이 오지 않은 상태로 코딩을 시작한 것이다.

계속 되는 오답행진 끝에 연속하는 회전을 저장하는 방법을 새로 짜기로 마음을 먹었고, vector를 사용해서 이어 붙였다. 이를 통해서 연속적인 회전을 구현할 수 있었다.

 

아래는 코드이다.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
 
int ba[5][8];
 
void connect(int num, int dir, vector<pair<int,int>> &chain) {
    int ndir = dir;
    //왼쪽으로 가면서 찾는다.
    for (int i = num; i >= 2; i--) {
        //다른 극이면
        if (ba[i][6] + ba[i - 1][2] == 1) {
            //옆에 바퀴는 반대 방향으로 돌아야 하니까 -1을 곱해준다.
            chain.push_back(make_pair(i - 1, -1 * ndir));
            //그 다음 거는 또 방향이 바껴야 하니까 -1을 곱해준다.
            ndir *= -1;
        }//같은 극이면 더이상 가지 않는다.
        else break;
    }
    ndir = dir;
    //오른쪽으로 가면서 찾는다.
    for (int i = num; i < 4; i++) {
        if (ba[i][2] + ba[i + 1][6] == 1) {
            chain.push_back(make_pair(i + 1, -1 * ndir));
            ndir *= -1;
        }
        else break;
    }
}
 
void change(int num, int dir) {
    //시계 방향
    if (dir == 1) {
        int temp = ba[num][7];
        for (int i = 7; i >= 1; i--) {
            //앞에 거를 땡겨준다.
            ba[num][i] = ba[num][i - 1];
        }
        ba[num][0] = temp;
    }
    else {
        int temp = ba[num][0];
        for (int i = 0; i < 8; i++) {
            //뒤에 거를 앞으로 땡겨온다.
            ba[num][i] = ba[num][i + 1];
        }
        ba[num][7] = temp;
    }
}
 
int main(int argc, char** argv) {
    int k;
    for (int i = 1; i < 5; i++) {
        for (int j = 0; j < 8; j++) {
            scanf("%1d", &ba[i][j]);
        }
    }
    //ba[i][0]이 12시에 있는 것.
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int num, dir;
        scanf("%d %d", &num, &dir);
 
        //돌려야 할 것들을 vector에 넣는다. dir도 넣어줘야 반대 방향으로 돌려줄 수 있다.
        vector<pair<int,int>> chain;
        chain.push_back(make_pair(num, dir));
        connect(num, dir, chain);
 
        //돌아야 할 것들 다 돌려준다.
        for (int i = 0; i < chain.size(); i++) {
            change(chain[i].first, chain[i].second);
        }
 
        /*출력(디버깅))
        for (int i = 1; i < 5; i++) {
            printf("%d번 째 바퀴: ", i);
            for (int j = 0; j < 8; j++) {
                printf("%d", ba[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        printf("(%d , %d) ", ba[1][2], ba[2][6]);
        printf("(%d , %d) ", ba[2][2], ba[3][6]);
        printf("(%d , %d)", ba[3][2], ba[4][6]);
        printf("\n");
        */
    }
 
    //0이면 그대로고 1이면 곱해서 출력
    printf("%d\n", ba[1][0] + ba[2][0] * 2 + ba[3][0] * 4 + ba[4][0] * 8);
 
    return 0;
}

------------------------------------------------------------------------------------------------------------------------------

굳이 돌아야 할 바퀴들을 vector로 연결해 줄 필요가 없다.

어짜피 연속적으로 왼쪽, 오른쪽으로 진행하기 때문에 극이 같을 경우 break를 통해서 멈춰주기만 하면 된다.

그냥 int 배열을 선언해서 돌아야할 바퀴들의 dir만 저장해 주면 된다.

코드가 좀 더 간단해 진다.

주의할 점은 dir 저장을 위한 배열을 전역 변수로 선언했기 때문에 초기화가 필요하다. 항상 vector, 배열, queue 등을 사용할 때 초기화할 필요가 있는 지를 잘 찾아보자.

 

그리고 입력을 받을 때 문자열로 들어오고, 받은 문자열을 굳이 숫자로 변환하여 계산하는 문제가 아니기 때문에 string 자료형을 갖는 vector를 사용하여 입력을 받으면 편하다.

 

마지막으로 답을 출력할 때, 각 바퀴의 0번 index에 2의 제곱수를 계속 곱하는데, 이를 shift 연산으로 처리하는 방법도 있다. 2의 제곱수를 할 때 shift 연산을 사용할 수도 있다는 것을 기억해둬야 겠다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int ba_dir[4];
 
int main() {
    vector<string> ba(4);
    
    for (int i = 0; i < 4; i++)cin >> ba[i];
 
    int k;
    cin >> k;
 
    for (int i = 0; i < k; i++) {
        int obj, dir;
        cin >> obj >> dir;
 
        for (int j = 0; j < 4; j++)ba_dir[j] = 0;
        obj--;
        ba_dir[obj] = dir;
        //회전 할 바퀴를 기준으로 왼쪽으로 가면서 회전 해야 하는 바퀴들에게 회전 방향을 정해준다.
        for (int j = obj - 1; j >= 0; j--) {
            //만약 극이 다른 경우에는 회전 해야 한다.
            if (ba[j][2] != ba[j + 1][6]) {
                ba_dir[j] = -ba_dir[j + 1];
            }
            else {
                //극이 같은 경우에는 break 시켜서 그 왼쪽부터의 바퀴는 회전시키지 않는다.(핵심)
                break;
            }
        }
        //회전 할 바퀴를 기준으로 오른쪽으로 가면서 회전 해야 하는 바퀴들에게 회전 방향을 정해준다.
        for (int j = obj + 1; j < 4; j++) {
            //만약 극이 다른 경우에는 회전 해야 한다.
            if (ba[j][6] != ba[j -1][2]) {
                ba_dir[j] = -ba_dir[j - 1];
            }
            else {
                //극이 같은 경우에는 break 시켜서 그 왼쪽부터의 바퀴는 회전시키지 않는다.(핵심)
                break;
            }
        }
        //여기까지 하면 방향이 다 정해지고, 회전하지 않는 바퀴는 처음에 0으로 초기화 되므로 회전하지 않는다.
        for (int j = 0; j < 4; j++) {
            int temp;//바퀴를 돌리기 전에 임시 저장할 변수
            if (ba_dir[j] == -1) {//반 시계 방향
                temp = ba[j][0];
                for (int k = 0; k < 7; k++) {
                    ba[j][k] = ba[j][k + 1];
                }
                ba[j][7] = temp;
            }
            else if (ba_dir[j] == 1) {//시계 방향
                temp = ba[j][7];
                for (int k = 7; k >= 1; k--) {
                    ba[j][k] = ba[j][k - 1];
                }
                ba[j][0] = temp;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        if (ba[i][0] == '1') {
            ans |= (1 << i);
        }
    }
    printf("%d\n", ans);
 
    return 0;
}