14891

내가 해결한 방법

시간초과가 발생했다. 극적으로 O(N^2)에서 logN 혹은 더 낮은 시간복잡도로 내릴 수 있을지 고민해봤지만 없었다. 그래서 불필요하게 연산되는 곳을 찾아보려고 한 결과 다음 코드를 발견했다.

첫번쨰 while문의 왼쪽으로 돌 때 else if문을 보자. 왼쪽 회전 번호와 첫번째로 회전할 바퀴번호가 같은 경우에만 break를 하게 된다. 이렇게 되면 왼쪽 회전 번호가 더이상 회전할 필요가 없을 경우에 break하지 못한다.

이해가 되지 않으면 오른쪽 회전과 비교하면 된다.

여튼 여기서 더이상 회전할 필요가 없는데 회전하고 있었고, 오른쪽 회전과 동일하게 진행하면 된다.

while(leftTempNum >= 0) {
    // 왼쪽으로 바퀴 인덱스 -1씩 해가며 회전시키기
    int prevNum = leftTempNum - 1;
    if(prevNum < 1) {
        break;
    }
    // 2번과 6번이 다르면 왼쪽으로 진행
    if(wheel[leftTempNum][6] != wheel[prevNum][2]) {
        leftTempNum -= 1;
    } else if(leftTempNum == wNum) {
        // 얘만 회전
        break;
    }
}

while(rightTempNum < 4) {
    // 오른쪽으로 바퀴 인덱스 +1씩 해가며 회전시키기
    int nextNum = rightTempNum + 1;
    if(nextNum > 4) {
        break;
    }
    if(wheel[rightTempNum][2] != wheel[nextNum][6]) {
        rightTempNum += 1;
    } else {
        break;
    }
}

/**
 * rotation - 1: 시계, -1: 반시계
 */
void rotate(vector<int> &wheel, int rotation) {
    // 시계 방향 회전
    if(rotation == 1) {
        int temp = wheel[7];
        for(int i = 6; i >= 0; i--) {
            wheel[i+1] = wheel[i];
        }
        wheel[0] = temp;
    }
    // 반시계 회전
    else {
        int temp = wheel[0];
        for(int i = 0; i<=7; i++) {
            wheel[i] = wheel[i+1];
        }
        wheel[7] = temp;
    }
}

int findWheelNumRequiredRotation(vector<int> wheel[], string command, int startWheelNum) {
    int resultWheelNum = startWheelNum;
    if(command == "Left") {

        while(resultWheelNum >= 0) {
            // 왼쪽으로 바퀴 인덱스 -1씩 해가며 회전시키기
            int prevNum = resultWheelNum - 1;
            if(prevNum < 1) {
                break;
            }
            // 2번과 6번이 다르면 왼쪽으로 진행
            if(wheel[resultWheelNum][6] != wheel[prevNum][2]) {
                resultWheelNum -= 1;
            } else {
                // 얘만 회전
                break;
            }

        }
    }

    else if(command == "Right") {
        while(resultWheelNum < 4) {
            // 오른쪽으로 바퀴 인덱스 +1씩 해가며 회전시키기
            int nextNum = resultWheelNum + 1;
            if(nextNum > 4) {
                break;
            }
            if(wheel[resultWheelNum][2] != wheel[nextNum][6]) {
                resultWheelNum += 1;
            } else {
                break;
            }
        }

    }
    return resultWheelNum;
}

int main(int argc, const char * argv[]) {
    vector<int> wheel[9];

    // 톱니 4개 입력 받기
    for(int i = 1; i<=4; i++) {
        for(int j = 1; j<=8; j++) {
            int temp;
            scanf("%1d", &temp);
            wheel[i].push_back(temp);
        }
    }

    // 움직이는 횟수
    int moveLength;
    cin>>moveLength;
    // 톱니 번호, 시계/반시계

    for(int i = 0; i<moveLength; i++) {
        int wNum, rotation;
        cin>>wNum>>rotation;
        int leftEndNum = findWheelNumRequiredRotation(wheel, "Left", wNum);
        int rightEndNum = findWheelNumRequiredRotation(wheel, "Right", wNum);


        // 왼쪽(본인 포함) 회전
        int tempRotation = rotation;

        for(int i = wNum; i>=leftEndNum; i--) {
            rotate(wheel[i], tempRotation);
            tempRotation = tempRotation == 1 ? -1 : 1;
        }


        tempRotation = rotation;
        for(int i = wNum + 1; i<=rightEndNum; i++) {
            tempRotation = tempRotation == 1 ? -1 : 1;
            rotate(wheel[i], tempRotation);
        }
        // 오른쪽 (본인 제외) 회전
    }

    int result = 0;
    int pow = 1;
    for(int i = 1; i<=4; i++) {

        result = result + (wheel[i][0]) * pow;
        pow <<= 1;
    }

    cout<<result<<endl;

    return 0;
}