백준 1158번 : 요세푸스 문제

문제

---

1158번: 요세푸스 문제 (acmicpc.net)

1158번: 요세푸스 문제

환형 링크드 리시트의 삭제 구현 문제

 

아이디어

---

• 환형 링크드 리스트를 직접 구현하자.
• class Node : 정수형 data와 다음 Node에 대한 정보 next를 필드로 갖는 클래스
• class Circle : Cirlcle에 접근할 수 있는 유일한 통로인 head와 삽입, 삭제 연산에 대한 메소드가 있는 클래스
• addData : 탐색용 노드 cur이 head에서 시작해서 next가 null이 될 때까지 이동시킨다.
  next가 null이 되었다는 것은 그 리스트의 끝에 도달했다는 뜻이므로 cur.next = new Node(data)를 해준다.
• addLastData : ❗환형을 만드는 핵심 메서드❗
  addData와 같은 방법으로 새로운 노드를 추가한 다음, 새로운 노트의 next를 head와 연결시켜준다.
  cur.next.next = this.head;
• removeData : ❗실수하기 쉬운 메서드❗
  case1️⃣ { circle의 크기가 1인 경우 => head의 next가 head와 동일한 경우 } : 헤드의 데이터를 리턴한다.
  case2️⃣ { K가 1이 아닌 경우 } : cur을 K-1번 움직여 삭제하려는 노드 이전 노드를 알 수 있다. 
  이전 노드가 최종 cur이므로, cur.next = cur.next.next; 로 cur 다음 노드를 건너뛰게 할 수 있다.
  case3️⃣ { K가 1인 경우 } : for문으로 이전 노드를 알 수 없으므로 cur의 next가 startNode가 될 때까지 움직인다.
  🔸모든 삭제 후에는 삭제한 노드 다음 노드를 세로운 head로 바꿔줘야 한다.

import java.util.ArrayList;
import java.util.Scanner;

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        next = null;
    }
}

class Circle {
    Node head;

    Circle() {
        this.head = null;
    }

    // 삽입하는 연산
    void addData(int data) {
        if (this.head == null) {
            this.head = new Node(data);
        } else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(data);
        }
    }

    void addLastData(int data) {
        if(this.head == null){ // 처음 추가하는 데이터가 head이자 끝인 경우
            head = new Node(1);
            head.next = head;
        } else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(data);
            cur.next.next = this.head;
        }
    }

    int removeData(int K) {
        Node cur = this.head;
        int delete = 0;

        // circle의 크기가 1인 경우
        if (cur.next.data == head.data) {
            delete = head.data;
        }

        // K가 1이상인 경우
        for (int i = 0; i < K ; i++) {
            if (i == K - 2) {
                // cur = 지울 노트 이전의 노드
                delete = cur.next.data;
                cur.next = cur.next.next;
                head = cur.next; // 삭제 후 헤드를 변경
            } else {
                cur = cur.next;
            }
        }

        // K가 1인 경우
        if(K==1){
            delete = head.data;
            while (cur.next != head){
                cur = cur.next;
            }
            cur.next = cur.next.next;
            head = cur.next; // 삭제 후 헤드를 변경
        }

        return delete;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 총 인원 수
        int K = scanner.nextInt(); // 제거할 순번

        // 링크드 리스트 생성과 삽입
        Circle ll = new Circle();
        for (int i = 1; i <= N; i++) {
            if(i == N){
                ll.addLastData(i);
            } else {
                ll.addData(i);
            }
        }

        ArrayList<Integer> answer = new ArrayList<>();
        for(int i = 0; i<N; i++) {
            answer.add(ll.removeData(K));
        }
        answer.add(ll.head.data);

        StringBuilder sb = new StringBuilder();

        sb.append("<");
        for(int i =0; i<N;i++){
            sb.append(answer.get(i));
            if(i==N-1){
                break;
            }
            sb.append(", ");
        }
        sb.append(">");
        System.out.print(sb);
    }
}