백준 9519번 졸려

🔒[문제 url]

https://www.acmicpc.net/problem/9519

🔑알고리즘

정해진 규칙을 반복하다보면 처음과 같아지는 상태,즉 한 cycle의 길이를 알 수 있게된다.
$x$의 범위가 매우 크므로, x % cycle만큼 반복하여 시간을 단축한다.

• cycle은 어떻게 구하는가?
  • 깜박인 후의 문자열이 주어지므로, 문제에서 요구한 내용을 처음 상태와 같아질때까지 반대로 반복한다.
  • 뒷부분의 길이만큼 옮기게 되며, 앞에서부터 만나는 홀수 index의 문자를 가장 뒤에서부터 앞으로 붙여나간다.
    따라서, stack을 이용해 홀수 index의 문자를 담아놓고 차례대로 뒤에 붙인다.
    
    
• 위 과정을 구한 cycle의 크기로 $x$에 나머지 연산을 적용한 값만큼 규칙을 다시 반대로 적용하면, 깜박이기 전의 문자열을 알게된다.

🐾부분 코드

bool Move()
{
    stack<char> st;//이동할 문자 저장
    int cnt = (len-1)/2; // 뒷부분 길이
    bool isOdd = false; // 홀수 idx만 이동하므로 매번 갱신
    for(int i = 0; cnt; i++)
    {
        if(isOdd)
        {
            isOdd = false;
            st.push(change[i]);
            change.erase(change.begin() + i);
            i--; // 하나씩 당겨지므로 index 조정
            cnt--;
        }
        else isOdd = true;
    }
    // 이동할 문자들을 뒤에 붙여줌
    while(!st.empty()) change += st.top(),st.pop();

  

<규칙 적용 함수>
규칙을 한 번 적용하는 함수이다.
뒷부분의 길이cnt를 구한 후, isOdd 변수를 통해 홀수 index를 구별하여 해당 위치의 문자를 stack에 push한다.
push할 때마다 cnt는 1 감소하고, 0이 되면 push를 종료한다.
stack에 담긴 문자를 다시 문자열의 뒤에 차례대로 붙여준다.

void SOLVE()
{

    // cycle 구하기
    int cycle = 0;
    while(true)
    {
        cycle++;
        if(Move()) break;
    }

    // cycle의 크기로 나누어 시행
    x %= cycle; 

    // cycle만큼 이동
    for(int i = 0; i < x; i++) Move();
    
    cout << change;


}

<전체 알고리즘>
위에서 설명한 알고리즘에 따라 구현한다.

🪄전체 코드

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int x;
string origin,change;
int len;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> x >> origin;
    len = origin.length();
    change = origin;
}

bool Move()
{
    stack<char> st;//이동할 문자 저장
    int cnt = (len-1)/2; // 뒷부분 길이
    bool isOdd = false; // 홀수 idx만 이동하므로 매번 갱신
    for(int i = 0; cnt; i++)
    {
        if(isOdd)
        {
            isOdd = false;
            st.push(change[i]);
            change.erase(change.begin() + i);
            i--; // 하나씩 당겨지므로 index 조정
            cnt--;
        }
        else isOdd = true;
    }
    // 이동할 문자들을 뒤에 붙여줌
    while(!st.empty()) change += st.top(),st.pop();

    return origin == change;
}

void SOLVE()
{

    // cycle 구하기
    int cycle = 0;
    while(true)
    {
        cycle++;
        if(Move()) break;
    }

    // cycle의 크기로 나누어 시행
    x %= cycle; 

    // cycle만큼 이동
    for(int i = 0; i < x; i++) Move();
    
    cout << change;


}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

cycle을 직접 구하려다가.. 규칙을 찾기 힘들어서 생각하다보니 '컴퓨터한테 시키면 되는걸 왜 내가 하고있냐ㅋㅋㅋ' 했던 문제..
문자열 알고리즘은 아는게 쥐뿔도 없어서 Move() 함수가 결코 효율적이지 않을거라는 생각이 들었지만, 문자열 심화 공부는 조금 미뤄두도록 하자...
재미없어..! 서만은 아니고 우선순위 높은 것부터~