Daily Leetcoding Challenge 1535. Find the Winner of an Array Game

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

Find the Winner of an Array Game - LeetCode

그동안 풀었지만 포스팅 안 한 문제들이 꽤 있어서 문제 풀었던 방식을 기록해 두면 좋을 것 같은 문제들 기준으로 남겨두려고 한다.

직관

가장 단순하고 직관적인 방법은 게임을 시뮬레이션하는 것이다. 첫번째첫 번째 숫자와 다음 숫자들을 비교하고, 큰 숫자는 첫 번째 자리로 이동하고 작은 숫자는 배열 끝으로 이동하면서 k번 이길 때까지 반복한다. 비교하면서 큰 숫자는 winner에 저장하고, 나머지 숫자는 큐에 넣어서 비교를 반복하면 된다. 에지 케이스를 살펴보자. k가 winner를 제외한 나머지 원소보다 큰 경우, 그 이상 비교해 봤자 winner는 그 배열에서 가장 큰 원소가 될 것이다.

접근법

배열의 첫번째 원소는 winner로 저장하고, 배열의 나머지 원소는 q에 넣는다. q에서 원소를 하나씩 빼서 winner와 비교하여 값이 winner보다 크면 winner를 바꾸고, 아니면 count를 1 증가시킨다. count가 k와 같거나 count가 큐의 크기보다 큰 경우(winner가 arr에서 가장 큰 수인 경우), 루프를 탈출한다.

복잡도

배열 arr의 크기를 n이라고 하자. 시간복잡도의 경우 배열의 모든 원소를 큐에 넣으면서 O(n), 그리고 반복문이 큐를 돌면서 최대 n개 원소를 확인할 수 있기 때문에 O(n)이 필요하다. 그래서 시간 복잡도는 O(n)이다. 공간 복잡도의 경우는 n개의 원소를 큐에 저장해야 하기 때문에 O(n)이다.

코드

공유된 솔루션을 찾아보면 추가로 메모리를 사용하지 않고(O(1)) 배열을 한 번만 순회하는 최적화된 솔루션이 있다. 아이디어는 비슷하니 코드를 참고해 보기 바란다.

내 솔루션

class Solution {
    public int getWinner(int[] arr, int k) {
        Queue<Integer> q = new LinkedList<>();
        int winner = arr[0];
        int count = 0;
        for(int i=1; i<arr.length; i++) {
            q.offer(arr[i]);
        }
        while(count < k && !q.isEmpty()) {
            int num = q.poll();
            if (winner > num) {
                count += 1;
                q.offer(num);
            } else {
                count = 1;
                q.offer(winner);
                winner = num;
            }
            if (count > q.size()) {
                break;
            }
        }
        return winner;
    }
}

최적화된 솔루션

class Solution {
    public int getWinner(int[] arr, int k) {
        int win = 0, cur = arr[0];
        for(int i=1; i < arr.length; i++) {
            if (arr[i] > cur) {
                cur = arr[i];
                win = 0;
            }
            if (++win == k) {
                break;
            }
        }
        return cur;
    }
}