99클럽 코테 스터디 34일차 TIL + 스택/큐(Find the Winner of the Circular Game)

오늘의 과제

리트코드 medium으로 분류된 Find the Winner of the Circular Game 입니다.

 

이번 유형은 스택/큐 입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

N이 주어질 때 K번째마다 요소를 제거하여 마지막 하나의 요소만 남을 때 까지 반복 후 해당 요소를 반환하면 됩니다.

 

이 문제는 요세푸스 문제의 변형으로 다음과 같은 수식을 갖고 풀 수 있습니다.

f(n, k) = (f(n - 1, k) + k) % n

 

단순 암기 문제로 코드 또한 위 수식이 전부입니다. 마지막 한 명이 남을 때 까지 재귀적으로 호출해주면 됩니다.

class Solution {
    public int findTheWinner(int n, int k) {
        return josephus(n, k) + 1;
    }
    
    private int josephus(int n, int k) {
        if (n == 1) {
            return 0;
        } else {
            return (josephus(n - 1, k) + k) % n;
        }
    }
}

 

 

다만 문제의 유형이 스택/큐인 만큼 큐를 활용한 풀이 방법도 존재합니다.

 

먼저 n만큼 친구들을 큐에 넣어줍니다.

Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
    queue.add(i);
}

 

그 후 k - 1만큼 큐에서 꺼내 다시 집어넣은 후 k번째에서 poll 합니다.

while (queue.size() > 1) {
    for (int i = 0; i < k - 1; i++) {
    	queue.add(queue.poll()); // K-1명의 친구를 뒤로 보냄
    }
    queue.poll(); // K번째 친구를 제거
}

 

조건에 의해 while문에서 탈출했다면 큐에 한 명만 남아있으니 그가 승자입니다.

return queue.poll();

 

 

전체 코드입니다.

public int findTheWinner(int n, int k) {
    // 큐 초기화
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 1; i <= n; i++) {
        queue.add(i);
    }

    // 게임 진행
    while (queue.size() > 1) {
        for (int i = 0; i < k - 1; i++) {
            queue.add(queue.poll()); // K-1명의 친구를 뒤로 보냄
        }
        queue.poll(); // K번째 친구를 제거
    }

    // 큐에 남은 마지막 친구가 승자
    return queue.poll();
}

 

배운 점

처음엔 문제 유형에 맞게 큐로 풀었습니다. 이후 리트코드 내 최적의 시간 효율을 찾아보니 일종의 공식이 있었는데 그게 요세푸스 문제라는 유명한 문제였습니다. 이전에 공부할 때 k만큼 돌아서 한 명씩 제거하는 형태의 문제를 분명히 많이 풀었었는데 왜 기억이 나지 않나 모르겠네요. 추후 유용하게 쓰일 수 있는 공식이니 기록에 남깁니다.

 

J(n, k) = (J(n - 1, k) + k) % n

 

 

오늘의 한줄평

둥글게 둥글게 빙글 빙글 돌아가며 춤을 춥시다.