[백준] 18192 - 보고 정렬

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

음... 정~~~~말 오랜만에 문제를 풀려고 앉았는데....

재밌는 문제라해서 들어가 봤더니 이런 세상에?? 마치 B형 시험과 같이, 주어지는 header나 cpp파일을 include 해야 되는 문제....

문제도 뭔가 되게 긴장되게 생겼지만, 문제가 B형에 비해서 상당히 허술하다....

비교를 하자면, B형은 내가 생각할 때 크게 두가지로 나뉘는 것 같다.

1. 충실히 구현만 하면 풀 수 있다. 하지만,,,, 최적화 부분에서 score가 메겨지는 유형

2. 구현이 거지같이 힘들거나 어려운 문제

그러나 이 문제는 그냥.... 허술하기 짝이 없다;;

주어지는 조건이라고는 함수 호출 2500번이 끝....

한마디로 주어지는 최적화 답과는 달라도, 통과되는건 ok라는 말...

결국... 생각보다 쉽게 풀렸다.... 아이디어는 아래와 같다

1. suffle_array()를 호출하기 위해서 st, ed를 정해주어야 하는데 이 st, ed를 어떻게 찾느냐가 관건인 것 같다.

구간을 정해놓고 모든 값을 정렬시키겠다는 것 보다는, st값은 key값으로 가지고, 이 st의 key값과 같은 값이 있는 arr의 좌표를 찾아 ed로 넣어준다. 이렇게 찾은 st, ed값을 가지고 suffle_array()를 호출한다.

2. 1의 방법을 반복하다가, st의 위치에 st값과 같은 값이 있게되면 break를 걸고 st를 올려준다.

3. sort가 완료되면 함수 종료

위의 링크에 들어가면 문제에 필요한 header와 cpp파일이 있으니 include하고 사용하면 된다.(main함수까지 친절하게 구현되어있음)

#include "bogoSort.h"
#include <algorithm>
 
bool compare(std::vector<int> origin_arr, std::vector<int> compare_arr) {
    for (int i = 0; i < origin_arr.size(); i++) {
        if (origin_arr[i] != compare_arr[i]) {
            return false;
        }
    }
    return true;
}
 
void sort_array(int N)
{
    std::vector<int> arr = copy_array();
    std::vector<int> compare_arr = arr;
    std::sort(compare_arr.begin(), compare_arr.end());
    int st = 0, ed = N - 1;
    while (!compare(arr, compare_arr)) {
        
        while (arr[st] != st) {
            for (int i = st; i < N; i++) {
                if (arr[i] == st) {
                    ed = i;
                    break;
                }
            }
            shuffle_array(st, ed);
            arr = copy_array();
        }
        //arr = copy_array();
        st++;
    }
}