99클럽 코테 스터디 34일자 TIL +find-the-winner-of-the-circular-game

문제 출처

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

학습 키워드

큐/스택

시도 방법

이 문제는 1을 시작으로 시계방향으로 n까지 사람들이 구성되어 있고 자신을 포함해 K만큼 이동한 후에 해당 대상을 삭제한다.
이를 반복해 최종적으로 남는 대상을 리턴하는것이다.

나의 경우 큐 방식을 활용해서 문제를 풀었다.

내가 작성한 코드

class Solution {
    public int findTheWinner(int n, int k) {
        
        Queue<Integer> circle = new LinkedList<>(); 

        for(int i = 1 ; i<=n; i++) {
            circle.offer(i); 
        }

        int pointer = 0; 
        while(circle.size() != 1) {
            
            int tmp = circle.poll(); 
            pointer++; 

            if(pointer < k) {
                circle.offer(tmp); 
            } else {
                pointer = 0 ;
            }
        }

        return circle.poll(); 
    }
}

코드설명

먼저 큐에 1~n까지 순서대로 삽입(offer)했다.
pointer를 이용해서 어떤 대상을 가리키고 있는지 확인하였으며
만약 현재 가리킨 포인터가 k와 같다면 해당 대상을 삭제한 후 pointer를 다시 0으로 설정했다.

이게 가능한 이유는 큐를 활용했기 때문인데 아래 예시로 예를 들어보자

queue = [1,2,3,4,5] , k = 2

pointer = 1 이고 k와 같지 않으므로 앞의 1을 뽑아 뒤에 추가한다.

queue = [2,3,4,5,1]

pointer = 2 이고 k와 같으므로 앞의 2를 뽑아 뒤에 추가하지 않는다.(삭제)

queue = [3,4,5,1]

이런 방식으로 반복해서 큐의 사이즈가 하나가 될때 이를 리턴한다.

출력결과

새롭게 알게된 점

없음

다음에 풀어볼 문제 - flatten-nested-list-iterator

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL