[C++] HackerRank 해커랭크 Gaming Array 풀이

최대값 찾기만 잘 이용하면 쉽게 풀 수 있는 문제인데 그걸 찾기가 쉽지 않았던

 

---

문제의 조건

1. 밥과 앤디가 게임을 하는데 

2. 정렬되지 않은 배열에서 최대값을 찾으면 최대값을 포함한 나머지 인덱스들을 지움

3. 남은 인덱스에서 또 최대값을 찾아서 2번 반복

4. 밥이 항상 첫번째로 시작하고 게임은 밥과 앤디의 턴이 번갈아가며 진행된다. 

5. 마지막으로 최대값을 찾아서 더 이상 진행할 수 없는 상태로 만든 사람이 이긴다. 

7. 배열 arr가 주어질 때 BOB과 ANDY 중 누가 이기는지 출력해라

 

---

정렬되어있지 않은 배열을 처음부터 순회하면서 최대값을 찾을 때마다 카운트를 증가시켜주면 됩니다. 

 

처음엔 문제에 속아서 반복문으로 최대값 찾은 후에 

또 반복문을 최대값 인덱스부터 돌려서 이후 값들을 0으로 바꾸고 그 때마다 카운트 증가시키고 ...

이걸 반복했는데 

타임아웃 뜨더라고용

ㅋㅋㅋ그럼 그렇지...

 

제시된 게임의 룰을 반대로 진행한다고 생각해보면 빠르게 탐색할 수 있는 코드를 작성할 수 있습니다. 

 

string gamingArray(vector<int> &arr) {
    
    int iMax = 0;
    int iCount = 0;
    
    for (int i = 0; arr.size() > i; i++)
    {
        if (iMax < arr[i])
        {
            //최대값은... 더 큰 수를 찾으면 찾았지 작은 수를 찾지는 않는다. 
            //[7,4,5,9,2] 배열에서 배열의 0번째부터 순회하면서 최대값을 찾는다면
            //iMax에 처음에는 7이 들어갈 것이고 그 다음에는 9가 들어갈 것이다. 
            //게임의 룰대로 적용해서 생각해보면 처음에 BOB이 9를 찾았을 때 9,2가 지워지고 7,4,5만 남으며
            //다음 ANDY가 7을 찾으면 나머지가 다 지워지고 ANDY가 이긴다. 
            //저걸 반대로 생각하면 아래와 같은 코드가 됨 
            iMax = arr[i];
            iCount++;
        }
    }
    
    //항상 BOB이 먼저 시작하기 때문에 카운트가 짝수면 ANDY 승, 홀수면 BOB 승
    string strWinner;
    if (0 == iCount % 2)
        strWinner = "ANDY";
    else 
        strWinner = "BOB";
    
    return strWinner;
}

 

오늘의 교훈은...

문제에 속지 말자 

ㅠ.ㅠ