본문 바로가기
알고리즘/백준

백준 1158 요세푸스 문제 (JAVA 자바 풀이)

by Renechoi 2023. 12. 28.

백준 1158 요세푸스 문제 (JAVA 자바 풀이)

 

 


 

 

문제

요세푸스 문제는 다음과 같다.

 

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

 

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

 

 


 

 

💡 풀이 과정

 

ArrayList와 환형 구조를 이용해서 풀어보자. 

 

K와 N에 대해 list로 초기화한다. 

 

List<Integer> circle = new ArrayList<>();
for (int i = 1; i <= N; i++) {
   circle.add(i);
}

 

계산 편의성을 위해 1 베이스로 초기화한다. 

 

 

이렇게 circle이 만들어졌으면 이제 k 번째 사람이 누구인지, 그 사람을 제거한 뒤 이어갈 인덱스가 필요하다. 

 

인덱스는 0으로 초기화하자. 

 

이때 답을 함께 기록하도록 StringBuilder를 사용한다. 

 

StringBuilder result = new StringBuilder();
result.append("<");

int index = 0;

 

 

이제 모든 사람에 대한 탐색을 시작하므로 while문을 리스트가 비어 있지 않을 때까지 돌리는 조건으로 설정한다. 

 

K 번째 옆에 있는 사람에 대해 제거를 해주어야 하므로 제거 대상의 인덱스는 다음과 같이 작성한다. 

 

index = (index + K - 1) % circle.size();

 

환형으로 관리를 하고 있으므로 사이즈를 모듈러로 취해준다. 

 

여기서 왜 -1을 해줄까? 다음과 같은 숫자를 생각해보자. 

 

1 2 3 4 5 6 7 에서 3번째 값인 3을 삭제할 것이다. 그러면 1 2 4 5 6 7이 된다. 이제 다음 번에 삭제할 인덱스는 6일 텐데 기존의 인덱스에 3을 더한 것을 생각해보면 6의 인덱스는 6이어야 할 것이다. 그런데 실제 6은 인덱스가 5이다. 그 이유는 3이 삭제 되면서, 즉 요소가 하나 삭제되면서 하나씩 밀리게 되었기 때문이다. 이를 고려하여 다음 요소 제거 대상을 계산할 때 K -1을 해준다. 

 

이제 주요 알고리즘은 모두 구현이 되었다. 

 

문제 요구 사항에 따라 컴마를 처리하고 마지막에 꺽쇠 괄호를 처리한 뒤에 출력해주면 된다. 

 

int index = 0;
while (!circle.isEmpty()) {
   index = (index + K - 1) % circle.size();
   result.append(circle.remove(index));
   if (!circle.isEmpty()) {
      result.append(", ");
   }
}
result.append(">");

 

이 알고리즘의 시간 복잡도는 어떠할까? 

 

N개의 데이터에서 대해서 우선 O(N)이 될 것이다. ArrayList에서 remove 연산이 O(N)이다. 따라서 총 O(N^2)의 시간 복잡도를 갖는다. 

 

 

 

💡 코드 구현

 

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {

   private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
      return new StringTokenizer(bufferedReader.readLine());
   }

   public static void main(String[] args) throws IOException {

      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      // BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = receiveInput(bufferedReader);
      int N = parseInt(stringTokenizer.nextToken());
      int K = parseInt(stringTokenizer.nextToken());

      List<Integer> circle = new ArrayList<>();
      for (int i = 1; i <= N; i++) {
         circle.add(i);
      }

      StringBuilder result = new StringBuilder();
      result.append("<");

      int index = 0;
      while (!circle.isEmpty()) {
         index = (index + K - 1) % circle.size();
         result.append(circle.remove(index));
         if (!circle.isEmpty()) {
            result.append(", ");
         }
      }
      result.append(">");

      System.out.println(result);
   }
}

 

반응형