New Year Chaos

https://www.hackerrank.com/challenges/new-year-chaos/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays 

New Year Chaos | HackerRank

 

 

시도 1) 이런저런 시도가 많아 코드가 엉망..ㅋㅋ

int getCount(const vector<int>& q, int index, int& min);


void minimumBribes(vector<int> q) {
    int bribesCnt = 0;
    int min = 0;
    for (int i = q.size()-1; i >= 0; --i) {
        int curBribes = getCount(q, i, min);
        if (curBribes > 2) {
            std::cout << "Too chaotic" << std::endl;
            return;
        }
        bribesCnt += curBribes;
        int a = bribesCnt;
    }

    std::cout << bribesCnt << std::endl;
}

int getCount(const vector<int>& q, const int index, int& min) {
    int cnt = 0;
    int value = q[index];
    int compare = 0;

    if (min > value) {
        min = value;
        // return 0;  , 오류
    }


    for (int i = index; i < q.size(); ++i) {
        compare = q[i];
        if (compare < value) {
            compare = q[i];
            ++cnt;
            if (min < compare) {
                min = compare;
            }
            if (cnt > 2) return cnt;
        }
    }

    return cnt;
}

 

 

결론부터 말하면 테스트케이스 6,7,8,9 에서 시간초과가 떠서 해결하지 못하고 있다.

1시간 정도는 이런저런 방법으로 시도해봤는데  

 

    if (min > value) {
        min = value;
        // return 0;
    }

위 부분으로 인덱스 역방향으로 탐색하며 최솟값을 구해 비교해 더 탐색하지 않으면 될 것 같은데

저렇게 하면 다른 TC 들이 실패한다.

 

문제 접근법이 잘 못 됐나보다.

조금 더 생각해 보자