[LeetCode] 1535. Find the Winner of an Array Game

https://leetcode.com/problems/find-the-winner-of-an-array-game/description/

Find the Winner of an Array Game - LeetCode

leetcode - Find the Winner of an Array Game

문제 유형 : 투 포인터

문제 난이도 : Medium

 

문제

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0, and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

 

중복없는 정수배열 arr과 정수 k가 주어집니다.

배열 맨 앞의 두 정수를 비교해서 더 큰 값은 맨 앞에 남고, 작은 값은 배열의 맨 뒤로 옮깁니다. 이렇게 한 라운드를 했을 때, 앞에 남는 수자가 승리한 것으로 여겨집니다.

 

한 숫자가 k번의 승리를 거둔 후에 게임이 종료됩니다.

어느 숫자가 최종 승리를 하는지 구하시오.

 

 

풀이

만약 k 가 arr의 크기보다 크거나 같다면, 무조건 배열에서 가장 큰 숫자가 최종 승자가 됩니다.

이 경우 k번의 승리를 할 수 있는건 가장 큰 숫자밖에 없기 때문입니다.

 

그렇지 않은 경우에는 시뮬레이션을 직접 돌리면 되는데, 실제로 배열에서 제거하고 붙이는 데에는 시간이 오래 걸립니다.

투 포인터를 이용하여 게임을 진행합니다:

1. 현재 숫자에서 최대 몇라운드 이길 수 있는지 계산하기

2. 최대 이길 수 있는 라운드가 k 이상이라면 그 숫자 반환.

3. 그게 아니라면 현재 숫자가 게임을 끝나게 한 숫자부터 게임 다시 시작. 여기서 승리 카운트는 1부터 시작해야한다.

4. 현재 숫자가 배열 안의 범위이거나, 최대 숫자를 만나면 반복 멈추기

 

코드

C++

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int maxNum = *max_element(arr.begin(), arr.end());
        const int n = arr.size();
        if(k >= n) return maxNum;

        int i = 0;
        int winround = 0;
        while(arr[i] != maxNum && i < n)  {
            int j = 1;
            while(arr[i] > arr[i+j]) {
                j++;
                winround++;
            }
            if(winround >= k) return arr[i];
            winround = 1;
            i += j;
        }

        return maxNum;
    }
};