개요

[HackerRank]NewYearChaos

접근 방식

총 세번에 걸쳐서 풀이를 변경하며 접근했다.

첫번째 시도(틀림)

앞에서부터 순회하며 해당 숫자가 자기 차례가 아닌 값만 탐색했다.

(2,1,3,4)을 예로 들어보자. 여기서는 2가 자신의 차례가 아니다,
2를 잘못된 인덱스 값을 저장하는 set에 2를 추가한다.

하지만 1은 이미 인덱스가 바뀌어버렸으므로 정상적으로 섰는데도 잘못된 인덱스가 되어버린다.
따라서 타겟 값을 cnt변수에 할당해놓고 현재 인덱스가 다음 타겟값인지만 비교한다.
처음에 오름차순으로 정렬이 되어있어서 생각한 방법이다.

따라서 함수를 따라가보면

1. cnt=1, index 0에는 2가 저장.
   cnt와 다른값이므로 2를 wrongnumber에 넣는다.
   wrongnumber에 값을 넣을 때 원래 있어야하는 인덱스와 현재 인덱스를 비교해
   2가 넘으면 too chaotic을 출력한다.
   (2의 원래 인덱스인 1 - 현재 인덱스 값 0) 1을 저장한다.

2. cnt=1 , index 1에 1. 정상적이므로 넘어간다.

3. cnt=2, index 2에 3. cnt와 다른값이다.
   하지만 wrongnumber에서 cnt=2 를 탐색해본다.
   존재하므로 cnt는 3이되고 정상적이다

4. cnt=4 , index3에 4 정상적이다.

아래는 해당 방식의 코드이다.

void minimumBribes(vector<int> q) {
    set<int> wrongNums;
    int cnt=1,sum=0;
    for(int i=0;i<q.size();i++){
        if(wrongNums.find(cnt)!=wrongNums.end()){
            cnt++;
            i--;
            continue;
        }
        if(q[i]!=cnt){
            if(q[i]-1-i>2) {
                cout<<"Too chaotic\n";
                return;
            }
            wrongNums.insert(q[i]);
            sum += abs(q[i]-1-i);
        }
        else
            cnt++;
    }
    cout<<sum<<"\n";
}

반례는 123654가 있다. 5가 정상적인 인덱스라 탐지가 안됨 그냥 6만 움직인거로
위 방식을 따라가보면 1,2,3 은 정상적인 인덱스이므로 패스하고,
6을 만났을 때 cnt값이 4이다.
따라서 sum에 2가 더해지고, 6은 set으로 저장된다.

그다음 숫자는 5다. cnt는 4이므로 5와 다르다.
따라서 비교하게 되는데 문제는 5가 원래 인덱스에 위치해있다.
bribe되어서 앞으로 나갔지만 6에 의해 원래 자리에 위치해있는 것이다.

따라서 sum에는 0이 더해진다.
이 문제를 방지하기위해 아래 코드로 변경했다,

//sum += abs(q[i]-1-i);
sum+=abs(q[i]-cnt);

하지만 이렇게 되면 아래 수열과 같은 반례에서 문제가 생긴다.
1 2 5 3 7 8 6 4

두번째 접근(틀림)

    int sum=0;
    for(int i=0;i<q.size();i++){
        if(q[i]-1 !=i){
            int tmp =i;
            //for(; tmp<q.size()-1 && q[i]-1 != tmp ; tmp++){
            for(; tmp<q.size()-1 && q[tmp]-1 != tmp ; tmp++){
                swap(q[tmp],q[tmp+1]);
            }
            if(tmp-i>2){
                cout<<" Too chaotic\n";
                return;
            }
            sum+=tmp-i;
        }
    }
    cout<< sum<<"\n";

그냥 swap으로 naive하게 구현해봤다.
반례는 25134 2를 옮기면 5가 첫번째인덱스로가는데 5를 탐지하지않아 실패했다.

세번째 접근(맞음)

결국 swap을 통해 직접 순서를 바꿔가는 방향으로 정하고
값이 큰 값부터 조사해 나가는게 맞다고 생각이 들었다.

그렇다고 매번 전체 수열을 순회하며 제일큰값을 찾을 순 없으므로
map자료구조를 통해 원래 인덱스와 값을 저장하며 관리했다.

cnt도 q.size()에서 시작해 cnt--로 내려가며 진행했고,
map[cnt]를 통해 해당 값의 인덱스를 바로 찾았다.

그리고 swap할때는 map의 인덱스도 같이 변경해주며 진행했다.

전체 코드

void minimumBribes(vector<int> q) {
    int sum=0,cnt=q.size(),cntIdx=0;
    //value,index
    map<int,int> m;
    for(int elem: q){
        m.insert({elem,cntIdx++});
    }

    while(cnt>0){   
        int idx= m[cnt];

        if(q[idx]-1 !=idx){
            if(q[idx]-1-idx>2){
                cout<<"Too chaotic\n";
                return;
            }
            int tmp =idx;
            for (; tmp<q.size()-1 && q[tmp]-1 != tmp ; tmp++){    
                m[q[tmp]]++;
                m[q[tmp+1]]--;
                swap(q[tmp],q[tmp+1]);
            }
            sum+=tmp-idx;
        }
        cnt--;
    }
    cout<< sum<<"\n";
}

생각

세번째 시도를 했을 때도 틀렸어서 뭔가 했었는데
순서를 또 신중히 안여겨서 생긴일이였다.

먼저 서로 인덱스를 변경해주고 swap을 해줘야 하는데,
swap을 해주고 인덱스를 변경하니 의도한 값이아닌 바뀌어버린 값의 인덱스를 변경해버린것이였다.

for (; tmp<q.size()-1 && q[tmp]-1 != tmp ; tmp++){    
	swap(q[tmp],q[tmp+1]);
    m[q[tmp]]++;
    m[q[tmp+1]]--;
}