[백준] 1158 요세푸스

💡문제 분석 요약

https://www.acmicpc.net/problem/1158

• 1부터 N번까지 원을 이루어 앉아있다.
• 모든 사람이 없어질 때까지 순서대로 K번째 사람을 삭제하기
• [제약 사항]
  • 전체 인원은 (1 ≤ K ≤ N ≤ 5,000)

💡알고리즘 설계

• 큐를 사용한 방법
  • 전체 사람의 수만큼 반복하면서 계속 0~삭제할 인덱스반복하며 삭제할 인덱스가 아니라면 큐에 다시 넣고 삭제할 인덱스 순서가 되면 값을 넣지 않고 출력한다.
  • 큐에 다시 순서대로 넣고 넣은 순서대로 다시 poll을 할 수 있으니 이 과정을 통해 사람이 원으로 앉았다는 것을 구현할 수 있다.
• 연결리스트를 사용한 방법
  • 리스트 중간의 요소들을 삭제하는 것이 빈번하므로 연결리스트 선택
  • 사람의 수만큼 반복문을 돌면서 삭제할 index를 모듈러 연산을 사용하여 계산 후 삭제

💡코드

1. 큐로 구현

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

public class 요세푸스 {
    public static void main(String[] args) throws Exception{
        new 요세푸스().solution();
    }

    public static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        StringTokenizer st = new StringTokenizer(br.readLine());

        int total = Integer.parseInt(st.nextToken()); // 전체 번호 개수
        int deleteIndex = Integer.parseInt(st.nextToken()); // 삭제할 index

        Queue<Integer> queue = new ArrayDeque<>();
        for(int i =1 ; i <= total; i++){
            queue.offer(i); // 순서대로 사람을 큐에 넣음 
        }

        while(!queue.isEmpty()){ // 큐에 사람이 없을 때까지 반복
            for(int i = 0 ; i < deleteIndex; i++){ // 삭제할 순서대로 반복
                if(i == deleteIndex-1){ // 삭제할 순서가 되면 삭제 
                    sb.append(queue.poll());
                }else{
                    queue.offer(queue.poll()); // 삭제할 순서가 아니면 나중에 삭제되기 위해 다시 큐에 넣음 (원모양을 유지)
                }

            }
            if(queue.size() ==0){ // 마지막 삭제라면 끝을 의미하는 >을 추가
                sb.append(">");
                break;
            }else{
                sb.append(", "); // 아직 삭제할 것이 있다면 , 을 추가하고 계속 삭제 진행
            }
        }
        System.out.println(sb);
    }
    }

1. LinkedList로 구현

import java.io.*;
import java.util.*;
public class 요세푸스 {
    public static void main(String[] args) throws Exception{
        new 요세푸스().solution();
    }

    public static void solution() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        StringTokenizer st = new StringTokenizer(br.readLine());

        int total = Integer.parseInt(st.nextToken()); // 전체 번호 개수
        int deleteIndex = Integer.parseInt(st.nextToken()); // 삭제할 index

        List<Integer> linkedList = new LinkedList<>(); // 번호를 저장할 연결리스트 -> 삭제연산이 빈번하므로 배열보다는 연결리스트로 선택
        for(int i = 1; i <= total; i++) {
            linkedList.add(i); // 전체 번호를 세팅
        }
        int targetIndex = 0; // 삭제할 index 저장 변수
        int cnt = 0; // 삭제횟수
        while(!linkedList.isEmpty()){ // 연결리스트에 값이 없어질 때까지 삭제 연산을 반복
            targetIndex = (targetIndex+deleteIndex-1)%(total-cnt);
            int num = linkedList.get(targetIndex); // 삭제할 index에 있는 값을 가져옴
            linkedList.remove(targetIndex); // 삭제함
            if(linkedList.size()==0){ // 만약 마지막 삭제연산이라면 >으로 출력하고 끝
                sb.append(num+">");
                break;
            }else{
                sb.append(num+ ", "); // 마지막 연산이 아니라면 ,을 출력하고 삭제 연산 계속한다.
            }
            cnt++;//삭제 횟수 저장

        }
        System.out.println(sb);
    }
}

💡시간복잡도

• 1. 큐로 구현
  • 총 사람의 수 = N이라고 하고 삭제 인덱스 = deleteIndex이라고 하자
  • 삭제(remove/poll) 연산이 O(1) 시간에 수행된다.
    • 하지만 삭제할 인덱스가 주어진 경우(deleteIndex) 해당 인덱스까지 요소를 재배치하는 과정이 필요하다.
  • 이 과정에서 매 삭제마다 최대 **deleteIndex**만큼 요소를 이동시켜야 하므로, 전체 시간 복잡도는 **O(N * deleteIndex)**가 된다.
  • 실행시간 = 248ms
• 1. LinkedList로 구현
  • 첫 번째 요소를 삭제하기 위해 O(N) 시간이 걸리고, 두 번째 요소를 삭제하기 위해서는 O(N-1) 시간이 걸리며, 이런 식으로 계속해서 마지막 요소를 삭제할 때까지 시간이 줄어듭니다. 이 과정에서 각 단계마다 소요되는 시간의 합은 다음과 같다. O(n)+O(n−1)+O(n−2)+...+O(1) = 등차수열의 합과 유사 ⇒ **O(N^2)**
  • 실행시간 = 204ms
• 따라서, LinkedList 보다 Queue로 구현하는 것이 비교적 효율적이라고 할 수 있다.

💡 틀린 이유

• 틀린 건 아니지만 시간 복잡도 계산을 잘못했다.
  • 최악의 경우인 삭제할 인덱스가 제일 마지막에 있을 경우
    • LinkedList로 구현한다면 → O(n(n+1)/2) 라고 생각했고
    • Queue일 경우 → while문을 N번 반복하고 for문을 N번 반복해서 O(N^2)라고 생각했다
    • O(n(n+1)/2) < O(N^2) 이므로 linkeList가 더 효율적이라고 생각했다.
  • 하지만 이는 2가지를 잘못 생각했다.
    • 1. Queue의 시간 복잡도를 잘못 생각한 것이다.
      • deleteIndex 값이 입력 크기 **N**에 관계없이 동일한 작업을 반복하므로 상수 시간으로 간주할 수 있다.
        • 즉, 매 반복마다 deleteIndex 위치의 요소를 삭제하는 작업이 **N**의 크기에 관계없이 일정한 비용으로 수행될 수 있다
        • 이는 **deleteIndex**의 값이 입력에 따라 변하지 않으며, 삭제 연산을 수행하는 위치가 고정되어 있다는 것이다.
      • 반면, **N**은 문제의 입력 크기를 나타내며, 문제를 해결하는 데 있어 전체적으로 고려되어야 하는 변수이다. **deleteIndex**가 상수라고 할 때, 우리는 이를 상수 시간 비용으로 고려할 수 있지만, **N**은 문제의 규모 자체를 나타내고, 전체 작업량이 **N**에 의해 결정된다. 따라서 **N**을 상수로 간주할 수 없다.
    • 1. 빅오 표기법은 입력 크기 **n**이 충분히 크면 최고차항 이외의 항들(예: 상수항, 저차항)은 전체 실행 시간에 미치는 영향이 상대적으로 미미하다는 점으로 생각하고 최고차항만 고려한다는 점이다.
      • ⇒ 빅오표기법으로 효율성을 고려하자

💡 틀린 부분 수정 or 다른 풀이

💡 느낀점 or 기억할정보

• 효율성 계산할 때 빅오 표기법으로 생각하기
• 입력 크기에 상관없는 값이면 상수로 생각하기

번외 - ArrayQueue

• 스택(Stack)과 다르게 인터페이스(QUEUE)를 구현하는 클래스를 사용해야한다.
  • 많이 사용되는 것은 LinkedList 클래스
  • Queue<Integer> queue = new LinkedList<>();
  • 성능이 좋은 것은 ArrayQueue
    • 조회 성능
      • ArrayDeque는 내부적으로 요소를 배열에 저장하기 때문에, 인덱스로 요소에 바로 접근할 수 있는 반면, LinkedList는 각 요소가 자신 다음에 연결된 요소를 참조하고 있어서, 특정 인덱스의 요소에 접근하려면 처음부터 해당 인덱스까지 모든 요소를 순회해야 한다. 따라서 LinkedList를 이용하는 것이 앞쪽 요소에 접근하는데 시간이 더 걸린다.
    • 삽입 삭제 성능
      • 큐의 앞과 뒤에서 빠르게 요소를 추가하고 삭제하는 경우 linkedlist보다 성능이 좋다
      • 하지만 그냥 큐의 앞과 뒤를 제외한 삭제의 경우 선형시간이 걸린다.
    • 하지만 ArrayQueue는 중간에 요소를 삽입하는 메소드가 없다. 따라서 중간에 요소를 삽입하는 기능이 필요한 경우는 LinkedList를 이용하는 것이 좋다.
• 인터페이스(QUEUE)를 구현하는 클래스
  1. LinkedList
  2. ArrayDeque
  3. PriorityQueue