[BOJ 9519, CPP] sleepy

Problem link

boj 9519

Classification

Implementations, Strings, Simulation

Description

This problem was initially solved by full exploration.

• Measure the length of the string first

• 0 ~ assign a vector of numbers equal to the length of the string

• Repeat and flip based on problem conditions

• Once flipped a number of times, utilize the corresponding hash value to place them in reverse order

• You can see the original look!

The most important thing to note here is that you can flip it over and over again, depending on the conditions of the problem, and the cycle will always come back the same as the initial array.

Once you've found the rule above and refined it, you can use the

• Measure the length of the string first

• 0 ~ assign a vector of numbers equal to the length of the string

  • check for a cycle from 1 to (length of string - 1) times

  • iterate over the total number of flips divided by the number of cycles to derive the hash

• If flipped a certain number of times, utilize that hash value to reverse the order

• You can see the original image!

It will look like this

    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 ;
		}
    }

Initially, we moved the array directly as shown above, but this caused some overhead because we had to move the entire array after the insert, so it took a little longer.

    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;
    }

Therefore, we used the above method to create the array in advance and insert the values one by one, so that the time is only used for the maximum length of the array.

Solving code

// 졸려

#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);
}