[BOJ 9519, CPP] 졸려

문제 링크

BOJ 9519

분류

구현, 문자열, 시뮬레이션

설명

이 문제에 대해서는 처음에는 완전 탐색을 통한 풀이를 진행했다.

• 문자열의 길이를 먼저 측정
• 0 ~ 문자열의 길이만큼의 숫자 벡터를 할당
• 문제 조건에 따라서 반복하여 뒤집기
• 횟수만큼 뒤집은 경우, 해당 해시값을 활용하여 역순 배치
• 원래 모습을 확인할 수 있다!

여기서 제일 중요한 점은 문제 조건에 따라서 반복해서 뒤집는 것인데 반복해서 뒤집을 경우, 반드시 초기 배열과 동일하게 돌아오는 주기가 돌아온다는 점이 핵심이다.

위 규칙을 찾은 이후 해당 부분을 세분화를 거치면

• 문자열의 길이를 먼저 측정
• 0 ~ 문자열의 길이만큼의 숫자 벡터를 할당
  • 1회부터 (문자열의 길이 - 1) 회까지 주기를 체크
  • 전체 뒤집는 횟수를 주기로 나눈만큼 반복하여 해시 도출
• 횟수만큼 뒤집은 경우, 해당 해시값을 활용하여 역순 배치
• 원래 모습을 확인할 수 있다!

이렇게 된다.

    for (int i = 1; i <= target_length - 1; i++)
    {
        for (int j = 0; j < target_length / 2; j++)
        {
            temp = result.back();
            result.pop_back();
            result.insert(result.begin() + 2 * j + 1, temp);
        }

		if (start_vector == result)
		{
			cycle = i;
			break ;
		}
    }

처음에는 위와 같이 배열을 직접 움직이는 방식으로 했는데 이렇게 될 경우 insert 이후의 배열이 전부 움직여야 해서 일종의 오버헤드가 발생하는 케이스라 시간이 조금 더 늘어나는 모습을 보였다.

    for (int i = 1; i <= target_length - 1; i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		if (start_vector == temp_vector)
		{
			cycle = i;
			break ;
		}
		else
			result = temp_vector;
    }

따라서 이후에는 위와 같은 방식을 활용해 배열을 미리 만들고, 값을 하나씩 집어넣는 방식을 활용하여 최대 배열의 길이만큼만 시간을 사용하도록 했다.

풀이 코드

// 졸려

#include <iostream>
#include <vector>

using namespace std;

vector<int> flicker_action(int target_length, int count);

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int flicker_number;
    string result_string, init_string;
    vector<char> string_vector;
    vector<int> idx_vector;

    cin >> flicker_number;
    cin.ignore();
    getline(cin, result_string);

    for (int i = 0; i < (int) result_string.length(); i++)
        string_vector.push_back(result_string[i]);
    

    idx_vector = flicker_action(result_string.length(), flicker_number);
    init_string.resize(result_string.length());

    for (int i = 0; i < (int) result_string.length(); i++)
        init_string[idx_vector[i]] = result_string[i];

    cout << init_string << endl;
    return (0);
}

vector<int> flicker_action(int target_length, int count)
{
    vector<int> result, temp_vector, start_vector;
	int cycle;

    for (int i = 0; i < target_length; i++)
        result.push_back(i);

	start_vector = result;
	cycle = 1;

    for (int i = 1; i <= target_length - 1; i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		if (start_vector == temp_vector)
		{
			cycle = i;
			break ;
		}
		else
			result = temp_vector;
    }

	result = start_vector;

    for (int i = 0; i < (count % cycle); i++)
    {
		temp_vector.clear();
		temp_vector.resize(target_length);
        for (int j = 0; j < target_length; j++)
        {
			if (!(j % 2))
				temp_vector[j] = result[j / 2];
			else
				temp_vector[j] = result[target_length - 1 - (j / 2)];
        }

		result = temp_vector;
    }

    return (result);
}