Canonical Cycle

문제 >

배열을 입력받아서 정규표현식으로 표현하게끔 함.

정규 표현식은 아래와 같은 규칙을 따른다.

1. 하나의 숫자로 만들어진 사이클도 다 표시한다.
2. 각 사이클에서 가장 작은 수를 사이클의 제일 앞에 둔다.
3. 여러 개의 사이클을 표시할 때는 사이클의 제일 앞 숫자가 감소하는 순서로 표기한다.

3 4 6 2 5 1 이라는 배열을 예시로 들어보겠음.

1	2	3	4	5	6
3	4	6	2	5	1

해당 배열은 ( 1, 3, 6 ) ( 2, 4 ) ( 5 ) 로 나누어 지게 됨.

왜냐면, 1번은 3번을 가리키고, 3번은 6번을 가리키고, 6번은 1번을 가리키고 있으니 ( 1, 3, 6 ) 사이클이 만들어 짐

2번은 4번을 가리키고, 4번도 2번을 가리키고 있음. -> ( 2, 4 ) 사이클임

5번은 5번을 가리키고 있으니까 혼자만 뱅글뱅글 도는 ( 5 ) 사이클임 

 

그럼 해당 배열을 정규 표현식으로 만들어 보겠음.

1. 하나의 숫자로 만들어진 사이클도 다 표시한다.

-> ( 1, 3, 6 ) ( 2, 4 ) ( 5 )

2. 각 사이클에서 가장 작은 수를 사이클의 제일 앞에 둔다.

-> ( 1, 3, 6 ) ( 2, 4 ) ( 5 )

3. 여러 개의 사이클을 표시할 때는 사이클의 제일 앞 숫자가 감소하는 순서로 표기한다.

-> ( 5 ), ( 2, 4 ), ( 1, 3, 6 )

 

정규표현식은 5 2 4 1 3 6 으로 나타낼 수 있음.

정규 표현식의 좋은 점은 괄호 표시가 없어도 어떤 사이클인지 알아 볼 수 있다는 것임.

각 사이클에서 가장 작은 수가 앞이니까 사이클간의 구분이 됨.

 

입력 >

테스트케이스 수 , 입력할 정수 갯수, 배열 입력

 

출력 >

입력받은 배열을 정규표현식으로 출력

 

입출력 예시 >

입력	출력
4 4 1 2 3 4 5 5 4 3 2 1 6 6 1 2 3 4 5 1 1	4 3 2 1 3 2 4 1 5 1 2 3 4 5 6 1

---

일단 입력받은 배열의 cycle을 찾아낸다.

int cycle[101]; //입력받은 배열
int checked[101]; //cycle을 찾아냈는지 아닌지 check용도 -1로 초기화됨, 해당하는 cycle이 cycleIdx에 몇번째로 들어가있는지
vector<vector<int> > cycleIdx; //cycle들을 이중배열로 저장.
vector<vector<int> > solve; //출력할 배열.

void rules(int n){
    for(int i=0;i<n;i++){
        findCycle(i);
    }
    cycleSort();
    printCycle();
}

cycle찾아내는 함수

int findCycle(int k){
    int i =k;
    if (checked[i]==-1){ //checked가 -1에서 변화가 있음 -> 사이클 체크했다는뜻
        vector<int> v; //해당 사이클이 들어가는 벡터
        v.push_back(i);
        checked[i] = cycleIdx.size(); // 사이클 생성
        while(cycle[i] != k+1){ // 사이클이 생성될때 까지 계속 찾기
            i = cycle[i]-1;
            v.push_back(i);
            checked[i] = cycleIdx.size();
        }
        int min = *min_element(v.begin(), v.end()); //이번 cycle의 최소값
        int minIdx = min_element(v.begin(), v.end()) - v.begin(); //최소값의 idx
        v.erase(v.begin() + minIdx); //최소값 밖으로 빼내기
        v.insert(v.begin(),min); //제일 앞에 두기
        cycleIdx.push_back(v); // cycleIdx에 이번 사이클 추가
        checked[i] = cycleIdx.size()-1;
        return checked[i]; //이번 cycle이 cycleIdx에 몇번째에 들어가있는지 return. 사실 필요없음.
    }else {
        return checked[i];
    }
}

사이클 다 찾아냈으면, 이제 3번째 규칙에 맞게 정리

스크롤 올리기 귀찮으니까 적어둠.

3번째 규칙 : 여러 개의 사이클을 표시할 때는 사이클의 제일 앞 숫자가 감소하는 순서로 표기한다.

void cycleSort(){
    int size = cycleIdx.size();
    vector<int> minList; //각 사이클의 최소값을 정리해 둘 idx
    for(int i=0;i<size;i++){
        minList.push_back(cycleIdx[i][0]); //각 사이클마다 0번째 에 최소값을 뒀었음
    }
    while(minList.size()>0){
    	//젤 큰 값을 앞에 두고 내림차순으로 정렬해야되니까 max값을 뽑음
        int maxIdx = max_element(minList.begin(), minList.end()) - minList.begin();
        solve.push_back(cycleIdx[maxIdx]);
        minList.erase(minList.begin()+ maxIdx); //solve에 추가한 값은 minList에서 빼버렷
    }
}

이제 출력하면 끗남.

void printCycle(){
    for(int i=0;i<solve.size();i++){
        for(int j=0;j<solve[i].size();j++){
        	//idx로 저장해 둬서 +1 해서 출력해야 됨니다
            cout<<solve[i][j] + 1 << " ";
        }
    }
    cout<<endl;
}

사실 문제 풀면서 계속해서 생각했던 알고리즘이 바껴서 변수명이 이상함.

근데 다 풀고나니까 다시 바꾸기 귀찮아서 걍 썼음.

특별하게 사용된 이론은 없음. 있나? 몰루?

문제 이해하는게 제일 힘들었음. 정규 표현식이 뭔지 이해하는데 제일 오래걸림...

문제 처음 접했을때