[백준] 요세푸스 문제(1158번): 커스텀 원형 연결 리스트로 해결하기

코드 힌트

문제 흐름

• n명의 사람들이 원형으로 앉아 있습니다.
• 매 k번째 사람을 제거하는 작업을 반복해 최종 순서를 출력합니다.
• 기본적으로 요세푸스 문제는 큐를 활용한 풀이가 일반적이지만, 이 코드는 원형 연결 리스트를 직접 구현해 해결합니다.

핵심 아이디어

• 원형 연결 리스트 구현: 각 노드가 자기 자신을 포함한 원형 구조를 형성합니다. 마지막 노드는 처음 노드를 참조하며 리스트의 끝이 없습니다.
• 현재 노드 추적: pointNode를 활용해 현재 노드를 추적하며, 매 k번째 노드를 제거합니다.
• 출력 최적화: StringBuilder를 사용해 제거된 노드의 순서를 효율적으로 출력합니다.

알고리즘 흐름

1. 리스트 초기화
   • CircularLinkedList 클래스에서 노드를 추가해 원형 연결 리스트를 구성합니다.
   • 첫 번째 노드는 startNode, 마지막 노드는 endNode로 관리됩니다.
2. k번째 제거
   • 현재 노드에서 k-1번 만큼 이동한 후 제거 대상 노드를 찾습니다.
   • 제거된 노드를 StringBuilder에 기록하고 리스트에서 제외합니다.
3. 반복 및 종료
   • 제거 작업을 n번 반복하며 리스트가 비어질 때까지 진행합니다.
   • 최종 출력 형식을 맞추기 위해 마지막 콤마를 제거합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        
        CircularLinkedList list = new CircularLinkedList(); // 커스텀 원형 연결 리스트 생성
        
        int n = in.nextInt(); // 사람 수
        int k = in.nextInt(); // 제거할 간격
        
        // 사람을 순서대로 추가
        for (int i = 1; i <= n; i++) {
            list.add(new Node(i)); // 원형 리스트에 사람 추가
        }
        
        // n번 제거 작업 수행
        for (int i = 0; i < n; i++) {
            list.remove(k); // k번째 노드를 제거
        }
        
        // 출력 형식 맞춤 (마지막 ", " 제거)
        CircularLinkedList.sb.setLength(CircularLinkedList.sb.length() - 2);
        System.out.println(CircularLinkedList.sb + ">");
    }
}

// 연결 리스트의 노드 클래스
class Node {
    int data;   // 노드의 값 (사람 번호)
    Node link;  // 다음 노드를 가리키는 링크
    
    Node(int n) {
        data = n; // 노드 생성 시 값 설정
    }
}

// 커스텀 원형 연결 리스트 클래스
class CircularLinkedList {
    
    Node startNode = null; // 리스트의 시작 노드
    Node endNode = null;   // 리스트의 끝 노드
    
    Node pointNode = null; // 현재 위치를 나타내는 노드 (k번째를 추적)
    
    static StringBuilder sb = new StringBuilder(); // 결과 출력을 위한 StringBuilder
    
    // 노드를 추가하는 메소드
    public void add(Node node) {
        // 리스트가 비어있을 경우 초기화
        if (startNode == null) {
            startNode = node;
            endNode = node;
            sb.append("<"); // 출력 포맷 시작
        } else {
            endNode.link = node; // 기존 끝 노드의 링크를 새 노드로 설정
            endNode = node;      // 새 노드를 끝 노드로 설정
        }
        endNode.link = startNode; // 마지막 노드가 첫 노드를 가리키게 함 (원형 연결 리스트)
    }
    
    // k번째 노드를 제거하는 메소드
    public void remove(int idx) {
        if (startNode == null) {
            throw new ArrayIndexOutOfBoundsException("요소가 없습니다."); // 예외 처리
        }
        
        // 처음 호출 시 초기화
        if (pointNode == null) {
            pointNode = startNode; // 첫 번째 제거 작업 시작
            idx--; // 0부터 시작하므로 idx를 감소
        }
        
        Node previousNode = pointNode; // 현재 노드의 이전 노드를 추적
        for (int i = 0; i < idx; i++) { // idx번째 노드로 이동
            previousNode = pointNode;   // 이전 노드 갱신
            pointNode = pointNode.link; // 다음 노드로 이동
        }
        
        previousNode.link = pointNode.link; // 현재 노드를 리스트에서 제거
        sb.append(pointNode.data).append(", "); // 제거된 노드 기록
        pointNode = previousNode; // 현재 위치를 이전 노드로 설정
    }
}