99클럽 코테 스터디 34일차 TIL Find the Winner of the Circular Game

 

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

 

 

 

 

deque

요세푸스

josephus

 

 

 

 

 

1.  문제 및 접근

 

 

 

 

1823. Find the Winner of the Circular Game

 

n명이 게임을 하는데, 1부터 n명까지 시계방향으로 돌아가고

k가 주어지면 1번부터 시작해k번 떨어진 수의 사람을 돌며 탈락시킴

원형이라 반복하며 마지막에 남은 친구가 승리하고 그 친구 반환

deque로 구현하면 쉬울 것 같다.

 

1,2,3,4,5 k =2  [1,3,4,5] -2, [1,3,5] -4, [3,5] -3 [5] winner 5

 

 

Constraints:

• 1 <= k <= n <= 500

 

 

 

2. 풀이

 

 

public int findTheWinner(int n, int k) {
   
    Deque<Integer> deque = new LinkedList<>();


    for (int i = 1; i <= n; i++) {

        deque.add(i);
    }



    while (deque.size() != 1) {

        for (int i = 0; i < k-1; i++) {
            if (deque.peekFirst() == 0) {
                deque.removeFirst();
                continue;

            }



            int now = deque.removeFirst();

            deque.addLast(now);


        }
        deque.removeFirst();

    }

    return deque.peek();



}

 

 

 

 

 

 

 

 

 

 

2-1. deque

 

 

 

99클럽 코테 스터디 17일차 TIL 구명보트

99클럽 코테 스터디 17일차 TIL 구명보트

 

간단한 deque 설명이고, 더 추가적으로 작성하자면

 

 

 

Java에서는 ArrayDeque 또는 LinkedList를 사용하여 양쪽 끝에서 요소를 추가하거나 제거한다.

 

 

• 속도:
  • deque는 리스트보다 양 끝에서 요소를 추가하고 제거하는 작업이 효율적.  deque가 양쪽 끝에서 O(1) 시간 복잡도로 동작
  • but 리스트는 양 끝에서 요소를 추가하고 제거하는 데 평균 O(n) 시간이 걸립니다.

 

 

 

주요 메서드 (양방향 삽입 삭제

• addFirst(): deque의 앞쪽에 요소를 추가
• addLast(): deque의 뒤쪽에 요소를 추가
• removeFirst(): deque의 앞쪽에서 요소를 제거하고 반환
• removeLast(): deque의 뒤쪽에서 요소를 제거하고 반환

 

 

 

2-2. deque 선언 및 요소 추가

 

 

 

 

LinkedList로 구현한 deque 선언

 

일반적인 add 사용 시 앞에서부터 추가된다.

 

 

 

ex) Deque =[1,2,3,4,5] ,  k= 2

 

 

 

 

 

 

 

 

2-3. deque로 빼고 넣기

 

 

 

마지막 남은 요소가 winner니까 반환하기 위해 size가 1이 될 때 까지 반복

 

 

k번째까지 돌기 위해, for문으로 앞에 요소를 빼고, 뒤로 더해주는 작업을 반복

 

 

끝나면 현재 앞에 위치한 요소가 현재 게임에서 k번째에 걸려 진 사람이 된다.

 

그 사람을 빼고, 다시 whlie문 반복

 

 

예시로 보자면,

 

ex) Deque =[1,2,3,4,5] ,  k= 2

 

 

 

 

 

1회차

 

시작시점  = Deque[1, 2, 3, 4, 5] , K = 2

 

• 2번을 빼기 위해, 1은 맨 뒤로  이동

 

이동시점 = Deque[2, 3, 4, 5, 1]   loser = 2

 

• 2번을 빼고, 다음 회차로 

 

종료시점 = Deque[ 3, 4, 5, 1]  

 

 

 

 

2회차

 

시작시점  = Deque[ 3, 4, 5, 1] , K = 2

 

• 4번을 빼기기 위해, 3은 맨 뒤로  이동

 

이동시점 = Deque[4, 5, 1, 3]   loser = 4

 

• 4번을 빼고, 다음 회차로 

 

종료시점 = Deque[5, 1, 3]  

 

 

 

 

 

3회차

 

시작시점  = Deque[5, 1, 3] , K = 2

 

• 1번을 빼기기 위해, 5은 맨 뒤로  이동

 

이동시점 = Deque[1, 3, 5]   loser = 1

 

• 1번을 빼고, 다음 회차로 

 

종료시점 = Deque[3, 5]  

 

 

 

 

 

4회차

 

시작시점  = Deque[3, 5] , K = 2

 

• 5번을 빼기기 위해, 3은 맨 뒤로  이동

 

이동시점 = Deque[5, 3]   loser = 5

 

• 5번을 빼고, 다음 회차로 

 

종료시점 = Deque[3]  

 

 

 

 

Winner = 3

 

 

 

 

 

2-4. k-1까지 반복 ?

 

 

사실 두개의 동작이 구분된다.

 

한번에 꺼내서 뒤에 넣고, 빼는 동작이 아닌 

 

1. 꺼내서 뒤에 넣고

2. 뺀다.

 

 

그래서 for문은 꺼내서 뒤로 넣는 작업만 반복하고

 

 

실제 loser(deque에서 제거)는 for문 밖에서 작동하기에 k-1까지 꺼내서 뒤로 넣고, 따로 제거

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 마무리 및 추가

 

 

 

 

 

deque로 접근하면 쉽고 빠르겠다 했는데,

 

gpt vs 나

 

 

 

내 시간을 보면 50ms라 이건 분명히 더 빠른 방법이 존재한다고 보인다..

 

leetcode를 보면 runtime 별 얼마나 빠르게 풀었나 ? 볼 수 있어 현재 내 위치를 확인할 수 있고,

 

다른 사람들은 더 효율적인 방법을 풀었는지 유추가 가능해 다른 방법을 떠올리기 좋은 것 같다..

 

내가 직접 떠올리진 못해서 ㅠㅠ

 

 

 

 

 

 

 

3-1. 요세푸스 문제(josephus)

 

 

 

요세푸스 문제라고 꽤나 유명한 문제였다..

예전엔 수학에 흥미가 없어 잘 몰랐다.

 

 

 

 

 

 

문제 해결 접근 방법은 두가지가 있다

 

 

1. 재귀적 접근법:
   • 기본적인 재귀적 접근법을 사용하면 시간 복잡도는 O(n)
   • josephus(n, k) 함수는 기본적으로 josephus(n - 1, k)의 결과를 이용하여 현재 단계의 결과를 계산
2. 비재귀적 접근법:
   • 이 방법은 시간복잡도가 O(n)이며, 반복문을 사용하여 문제를 해결
   • josephus(n, k)를 반복문을 통해 계산할 수 있습니다.

 

 

 

 

 

 

 

 

 

3-2. deque vs 요세푸스

 

 

 

 

deque는 O(n * k)이다 현재 요소의 이동과 삭제의 k를 n번 반복하니까..

 

반면 요세푸스는  O(n)의 시간 복잡도를 가진다.

 

 

deque는 확실히 직관적이기만 하고, 효율은 별로네

 

 

 

 

 

 

 

 

3-3. 요세푸스 구현

 

 

bottom-up 방식으로

 

n을 1명, 2명씩 늘려가면서 n명의 수까지 for문을 돌며 winner를 구해내는 방식

 

생존자 위치는 winner = (winner+ k) % i로 생존자 위치를 업데이트. 여기서 모듈러 연산을 사용하여

배열에서의 인덱스를 처리

 

 

0번째 index부터 시작한 winner에 +1로 return;

 

 

순환배열의 경우 모듈러 연산이 유리하고, 0을 baseIndex로 잡는 것이 편리하다고 한다.

 

 

 

 

 

 

 

 

3-4. 예제

 

 

 

우리는 탈락자를 제거하고 탈락자의 다음 index부터 시작해 계속 진행하다가 승자를 가려냈지만,

1명일 때의 승자, 2 ,3 계속 업데이트 해나가는 게 핵심

 

 

 

n = 5, k = 2

 

 

• n = 1명일 때: 생존자 위치는 0 
• n = 2명일 때: 생존자 위치는 (0 + 2) % 2 = 0
• n = 3명일 때: 생존자 위치는 (0 + 2) % 3 = 2
• n = 4명일 때: 생존자 위치는 (2 + 2) % 4 = 0
• n = 5명일 때: 생존자 위치는 (0 + 2) % 5 = 2

 

 

 

 

n = 1명일 때의 winner를 구하고 전 winner의 index에서 출발해서 k번 돌고, 모듈러 연산

 

 

 

 

 

 

 

 

 

3-5. 찐 마무리

 

 

 

 

 

역시 많은 방법들 중 제일 효율적인 방법으로 구현 하는 것은 많은 예제의 접근이 중요한 것 같다.

 

창의성이 새로 무에서 유를 만들어내는 영역이 아니라, 많은 기억들 속에서 조합되서 나온다고 알고 있다..

 

그래서 알파고에 엄청난 기보들을 넣고 거기서 창의성이 발휘되어 최적의 수를 만드는 방식으로 동작한다고 했으니

 

왜 내 기억들은 장기기억이 되지 못하는가 ? bios같은 기억력을 갖고 싶은데 나는 항상 ram, cache의 기억력이다

 

그렇다고 성능이 빠르지도 못한.. 제일 최악이다

 

원하는 것들만 장기기억할 수 있는 능력이 있음 좋겠네 그만 날아가~