JUNGOL 실력키우기 2255 : 섞기 수열

A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 

그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 

섞기는 현재 가지고 있는카드에서 섞기 수열의 각 숫자가 나타내는 위치에 있는 카드를 순서대로 뽑아서나열하는 것이다.

예를 들어, N = 6이고 섞기 수열이 [3, 2, 5, 6, 1, 4]라고 하자. 

카드의 처음 상태가 [A1, A2, A3, A4, A5, A6]일 때, 섞기를 한 번 실행하면 카드의 순서가 다음과 같이 된다.

[A3, A2, A5, A6, A1, A4]

이 상태에서 다시 한 번 섞기를 실행하면 카드의 순서가 [A5, A2, A1, A4, A3, A6]이 되고, 

다시 한 번 더 섞기를 실행하면 카드의 순서가 [A1, A2, A3, A6, A5, A4]가 된다. 

이렇게 섞기를 반복하면 카드의 순서가 처음 상태인 [A1, A2, A3, A4, A5, A6]이 된다. 

처음 상태로 돌아 올 때까지 반복한 섞기의 최소 횟수를 주어진 섞기 수열의 궤적이라 한다. 

임의의 섞기 수열이 주어졌을 때, 그 섞기 수열의 궤적을 구하는 프로그램을 작성하시오.

첫 번째 줄에 카드의 수 N이 주어진다. N은 1 이상 20,000 이하의 수이다.
두 번째 줄에 섞기 수열을 나타내는 N 개의 자연수가 빈칸을 사이에 두고 주어진다.

 

첫 번째 줄에 입력으로 주어진 섞기 수열의 궤적을 출력한다. 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.

[Copy] 6 3 2 5 6 1 4

[Copy] 6

 

---

 

뭔가 생각이 고착화 되어있는지 엄청 고민하면서 했는데 안되서 다른 블로그 글을 보고 풀었네요. 본인도 이건 실제로 돌면 안될 것 같은데... 하면서도 어떻게 다른 방법으로 처리할지 생각이 나질 않았구요... 무엇보다 저번에 풀었던 LCM과 GCD 함수를 더 간단히 할 수 있는거를 배웠군요.

 

#include <iostream>
 
using namespace std;
 
void Shuffle(int n, int *arr, int *nArr, int &count);
bool IsArraySorted(int n, int *nArr);
 
int main(void)
{
    int n;    // 정수의 개수(1~20,000)
    int *arr;        // 섞는 방법을 저장할 배열
    int *nArr;     // 실제 섞을 배열
    int count = 0;    // 섞기 수열의 궤적
 
    cin >> n;
 
    // 배열 동적 할당
    arr = new int[n];
    nArr = new int[n];
 
    // n개의 자연수 입력
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
 
    // 1~n까지 자연수를 실제 섞을 배열에 초기화
    for (int i = 0; i < n; ++i)
        nArr[i] = i + 1;
 
    // 다시 순서대로 돌아올 때 까지의 궤적을 구한다.
    // Shuffle 이후 nArr[0] == 1 일때
    // 1부터 n까지가 순서대로인지 검사
    // 아니면 계속 셔플 반복
    while (true)
    {
        Shuffle(n, arr, nArr, count);
        if (IsArraySorted(n, nArr))
            break;
    }
 
    cout << count << endl;
 
    // 배열 해제
    delete[] arr;
}
 
// 주어진 대로 섞어줄 함수
// 포인터로 입력되기에 출력이 필요하진 않음
void Shuffle(int n, int *arr, int *nArr, int &count)
{
    // 배열의 중복 초기화를 막기 위해 static으로 선언
    static int *temp = new int[n];
 
    // 배열의 첫 원소가 다시 1이 될 때까지 반복
    do
    {
        ++count;
        // 섞기
        // 임시 배열을 이용하여 배열 내부의 값 생각하지 않고 대입 가능
        for (int i = 0; i < n; ++i)
            temp[arr[i] - 1] = nArr[i];
 
        // 바뀐 위치를 다시 대입
        for (int i = 0; i < n; ++i)
            nArr[i] = temp[i];
    } while (nArr[0] != 1);
}
 
// 전체 배열을 돌면서 순서대로 정렬되어 있는지 판단한다.
bool IsArraySorted(int n, int *nArr)
{
    for (int i = 0; i < n; ++i)
    {
        // 하나라도 순서대로 되어있지 않은 경우 false 리턴(조기 리턴)
        if (nArr[i] != i+1)
            return false;
    }
    // 모두 순서대로 되어있는 경우 true 리턴
    return true;
}

 

 

#include <iostream>
 
using namespace std;
 
int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}
int lcm(int a, int b)
{
    return a / gcd(a, b)*b;
}
 
 
int Shuffle();
 
// 속도를 조금이라도 올리기 위해 전역으로 선언
int n;    // 정수의 개수(1~20,000)
int arr[20000];
bool checked[20000];
 
int main(void)
{
    cin >> n;
 
    // n개의 자연수 입력
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
 
    cout << Shuffle() << endl;
}
 
int Shuffle()
{
    int result = 1;
    for (int i = 0; i < n; ++i)
    {
        int cnt = 0; // 현재 섞기 회수
        int startNum = i + 1;
        int curNum = startNum;
        if (startNum == arr[startNum - 1])    // 안 움직이는 놈은 안건듬
            continue;
        if (checked[i])    // 한번 확인한 루트는 더 이상 안돔
            continue;
        while (true)
        {
            ++cnt;
            checked[curNum - 1] = true;    // 확인 체크
            curNum = arr[curNum-1];
            if (startNum == curNum)    // 처음으로 돌아온 경우 종료
                break;
        }
        result = lcm(result, cnt);    // 최소 공배수 구하기
    }
    return result;
}

 

 

JUNGOL) 문제은행) 실력키우기) 섞기 수열