Jumping on the Clouds

https://www.hackerrank.com/challenges/jumping-on-the-clouds/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup 

Jumping on the Clouds | HackerRank

 

문제 이해 및 분석

  1. 플레이어는 0 또는 1의 구름을 지나가야 한다.

  2. 1의 구름은 올라갈 수 없다.

  3. 0의 구름만 올라갈 수 있다.

  4. 0의 구름에서 +1또는 +2 인덱스 상위의 구름만 갈 수 있다.

  5. 끝까지 못가는 경우는 없다.

 

문제 풀이

 시작 인덱스에서 이동할 수 있는 최대 인덱스를 구한다.

 기준 인덱스 +1, +2 인덱스를 보고 어떤 구름을 밟을지 결정한다.

 

int jumpingOnClouds(vector<int> c) {
    int jumpCnt = 0;
    int currentCloudIndex = 0;
    for (int i = currentCloudIndex; i < c.size();) {
        if (c[i+1] == 0 && c[i+2] == 0) {
            currentCloudIndex = i + 2;
            ++jumpCnt;
        }
        else if (c[i+1] == 0 && c[i+2] != 0) {
            currentCloudIndex = i + 1;
            ++jumpCnt;
        }
        else if (c[i+1] != 0 && c[i+2] == 0) {
            currentCloudIndex = i + 2;
            ++jumpCnt;
        }

        i = currentCloudIndex;

        if (currentCloudIndex == c.size()-1) {
            break;
        }
    }

    return jumpCnt;
}

 

 

비트셋등 다른 효율적인 방법이 더 있을것 같지만 알고리즘 문제 형태에 먼저 익숙해 지는것이 목표