99클럽 코테 스터디 34일차 TIL + [LeetCode] 1823. Find the Winner of the Circular Game/스택/큐/JAVA풀이/원형리스트

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

[LeetCode] 1823. Find the Winner of the Circular Game/스택/큐/JAVA풀이

 

-원형리스트

원형리스트란, 리스트의 마지막 노드의 링크가 첫번째 노드를 가리기는 연결 리스트로 원형을 하고 있다. 

선행 노드의 포인터가 필요하다. 

 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

 

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1. Start at the 1st friend.
2. Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
3. The last friend you counted leaves the circle and loses the game.
4. If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
5. Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

 

Example 1:

Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2:

Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.

 

 

 

코드

---

//원형 리스트

import java.util.*;

class Solution {

    //연결리스트 노드 클래스 선언 
    public static class Node { 
        private int val;
        private Node next;

        public Node(int n){ //생성자
            this.val=n;
            this.next=null;
        }

    }

    public int findTheWinner(int n, int k) {
        
        Node newNode = new Node(1);
        Node last = newNode; //연결리스트 last포인터 

        for(int i=2;i<=n;i++){ //연결리스트 초기화 
            Node tempNode= new Node(i);
            last.next=tempNode;
            last=tempNode;
        }

        //현재 last포인터를 1로 옮겨줌 
        last.next=newNode;
        last=newNode;
        
        int cnt=1;
        Node prevNode=last; 

        if(k==1) //얼리리턴 
            return n;

        while(last.next!=last ){ //연결리스트의 노드가 하나만 존재할때까지 반복
            if(cnt==k){
                prevNode.next=last.next;
                last=last.next;
                cnt=1;
            }    
            else{
                prevNode=last;
                cnt++;
                last=last.next;
            }

        }

        return last.val;
    }

}

 

원형리스트를 생성하고,

prevNode(이전노드) last(현재노드) 설정하고,

k만큼 node를 이동하여 prevNode의 next와 last를 바꾸어주며, 연결리스트에 노드가 하나만 존재할때까지 while문을 반복한다.

 

 

3. 오늘의 회고

---

 

 

• static으로 함수나 변수를 선언하면, 프로그램 실행시 class 선언시 static영역에 자동으로 함께 선언되어 고정된 크기를 가지며, 별도로 new 선언하여 heap영역에 관리할 필요가 없다. 
• static의 장점은 메모리 영역에 고정된 크기를 가지기에 매번 인스턴스를 생성하며 낭비되는 메모리를 줄일 수 있으며, 객체를 선언할 필요가 없어 속도가 빠르다.
• static의 단점은, 프로그램 종료시까지 메모리에 할당된 채로 존재하여 프로그램 성능에 악영향을 줄 수 있으며, 객체지향적이지 못하다. 또한 Interface를 구현하는데 사용될 수 없다. 
• Heap 영역에는 주로 객체들이 할당되어 Garbage Collector의 관여를 받아 자동으로 메모리를 관리할 수 있다. 메모리를 공유하지 않는다. 
• 노드 클래스를 선언하여, 원형리스트를 사용해 풀었다. 
  
  

https://velog.io/@ho__sing/LeetCode-1823.-Find-the-Winner-of-the-Circular-Game-xbwyylit

[LeetCode] 1823. Find the Winner of the Circular Game

 

원형리스트를 사용하지 않은 풀이. 때로는 자료구조를 사용하지 않고 문제가 어떻게 구성되어있는지, 어떻게 풀어야하는지 논리적으로 접근하는 방법이 필요할 때도 있는 것 같다. 조세퍼스 문제 

 

논리적인 과정을 코드로 표현하자