백준 9519번 졸려(c++)

구현, 문자열, 시뮬레이션 알고리즘 문제이다. 

 

알고리즘 풀이

눈을 깜빡이는 횟수가 최대 10억인거로 보아서, 일반적인 반복문으로는 시간복잡도를 초과할 것이다.

그러므로 눈을 깜빡이는 횟수 N을 줄이는 어떤 방법이 존재한다.

이때, 주어진 문자열이 다시 원래대로 돌아오는 사이클이 존재하는 것을 알 수 있다.

또 사이클이 문자열의 길이와 상관없이 불규칙적인 것 또한 아는 것이 중요하다.

 

그러므로, 먼저 사이클의 횟수를 구하고 사이클의 횟수보다 눈을 깜빡이는 횟수가 더 많다면

둘을 나눠 남는 나머지를 구한다.

해당 나머지는 사이클을 돌고 난 뒤, 마저 깜빡이는 수이다.

해당 나머지만큼 실제로 문자를 옮겨준다면 문제는 풀린다.
-> 문자열의 이동규칙은 코드를 보며 파악하자.

#include <iostream>
#include <string>

using namespace std;


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

    int N, cnt = 0;
    string sen;
    cin >> N >> sen;

    string temp = sen;

    while(true) {
        string first = "", last = "";

        int point = sen.length() - 1;
        if(sen.length() % 2 == 1)
            point--;

        for(int j = point; j>=0; j-=2) {
            last += sen[j];
        }

        for(int j = 0; j<sen.length(); j+=2) {
            first += sen[j];
        }

        sen = first + last;
        cnt++;

        if(temp == sen)
            break;
    }
    if(cnt < N)
        N %= cnt;

    for(int i=0; i<N; i++) {
        string first = "", last = "";

        int point = sen.length() - 1;
        if(sen.length() % 2 == 1)
            point--;

        for(int j = point; j>=0; j-=2) {
            last += sen[j];
        }

        for(int j = 0; j<sen.length(); j+=2) {
            first += sen[j];
        }

        sen = first + last;
    }

    cout << sen;

    return 0;
}

코드 리뷰는 언제나 환영입니다!