SORTGAME 질문입니다.

  • firenin
    firenin

    사용한 방법은 입력받은 수열과 정렬한 수열이 다를 경우

    진행합니다.

    진행 방식은 정렬이 안된 구역의 첫 인덱스(noSortStartIndex)와,

    그 구역 내 가장 작은 수의 인덱스(minIndex) 를

    Reverse 를 하고, 카운트를 올리며 이것을 반복하는 방식입니다.

    *ex)
    Reverse(data, noSortStartIndex, minIndex);
    1. 3 4 1 2
    noSortStartIndex : 0
    minIndex : 2
    2. 1 4 3 2
    noSortStartIndex : 1
    minIndex : 3
    3. 1 2 3 4 정렬된 배열과 같으므로 종료

    주어진 테스트 케이스로는 원하는 결과가 나오는데

    어떤 부분에서 틀린지 잘 모르겠습니다.

    도와주세요.

    //https://algospot.com/judge/problem/read/SORTGAME
    #include <iostream>
    using namespace std;
    
    int C;
    int N;
    int data[8 + 1];
    int sortData[8 + 1];
    void Reverse(int nums[], int first, int end)
    {
        int temp = 0;
        int end_index = end;
        int half = (first + end) / 2;
        for (int i = first; i <= half; i++)
        {
            temp = nums[i];
            nums[i] = nums[end_index];
            nums[end_index] = temp;
            end_index--;
        }
    }
    void q_sort(int nums[], int left, int right)
    {
        int pivot, l_hold, r_hold;
        l_hold = left;
        r_hold = right;
        pivot = nums[left];
        if (left == right)
        {
            return;
        }
        while (left < right)
        {
            while ( (pivot <= nums[right]) && (left < right))
            {
                right--;
            }
            if (left != right)
            {
                nums[left] = nums[right];
                left++;
            }
            while ((pivot >= nums[left]) && (left < right))
            {
                left++;
            }
            if (left != right)
            {
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = pivot;
        pivot = left;
        left = l_hold;
        right = r_hold;
        if (left < pivot)
        {
            q_sort(nums, left, pivot - 1);
        }
        if (right > pivot)
        {
            q_sort(nums, pivot + 1, right);
        }
    }
    void QuickSort(int nums[], int size)
    {
        q_sort(nums, 0, size-1);
    }
    
    int main()
    {
        int noSortStartIndex = -1;
        int noSortEndIndex = -1;
        int min = 999999;
        int minIndex = 0;
        bool isSame = false;
        int count = 0;
        cin >> C;
        while (C--)
        {
            for (int i = 0; i < 8; i++)
            {
                data[i] = 0;
                sortData[i] = 0;
            }
            cin >> N;
            for (int i = 0; i < N; i++)
            {
                cin >> data[i];
                sortData[i] = data[i];
            }
            QuickSort(sortData, N);
    
            while (!isSame)
            {
                for (int i = 0; i < N; i++)
                {
                    if (data[i] != sortData[i])
                    {
                        break;
                    }
                    if (i == N - 1)
                    {
                        isSame = true;
                    }
    
                }
                if (isSame)
                    break;
    
                for (int i = 0; i < N; i++)
                {
                    if (data[i] != sortData[i])
                    {
                        if (noSortStartIndex == -1)
                        {
                            noSortStartIndex = i;
                        }
                        else
                        {
                            noSortEndIndex = i;
                        }
                    }
                }
    
                for (int i = noSortStartIndex; i <= noSortEndIndex; i++)
                {
                    if (min > data[i])
                    {
                        min = data[i];
                        minIndex = i;
                    }
                }
                Reverse(data, noSortStartIndex, minIndex);          
                count++;
                noSortStartIndex = -1;
                noSortEndIndex = -1;
                min = 999999;
                minIndex = 0;
            } // end of while(!isSame)
    
            cout << count << endl;
            count = 0;
            isSame = false;
        }
        return 0;
    }
    

    9년 전
2개의 댓글이 있습니다.
  • amok
    amok

    4 3 1 2 가 제시하신 알고리즘의 반례가 됩니다


    9년 전 link
  • firenin
    firenin

    감사합니다


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.