[알고리즘 PS] 백준 1158번 요세푸스 문제 자바 문제풀이 (큐, 연결 리스트 풀이)

문제

해당 포스팅은 백준의 1158번 요세푸스 문제 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이 문제는 큐 자료구조로 해결할 수 있는 대표적인 문제격이다.

 

문제는 이렇다.

 

1 ~ N 까지 수를 1자로 늘여놓는다.

N = 7

1, 2, 3, 4, 5, 6, 7

그리고 포인터를 K만큼 움직인 수를 출력하고 해당 리스트에서 제외시킨다.

 

이 과정을 리스트에 원소가 없을 때 까지 반복하는데, 다음과 같은 형태이다.

N = 7, K = 3

Rount 1
=> 1, 2, 3, 4, 5, 6, 7
=>       -
=> return => 3,

Rount 2
=> 1, 2, 4, 5, 6, 7
=>             -
=> return => 3, 6

Rount 3
=> 1, 2, 4, 5, 7
=>    -
=> return => 3, 6, 2

Rount 4
=> 1, 4, 5, 7
=>             -
=> return => 3, 6, 2, 7

Rount 5
=> 1, 4, 5
=>       -
=> return => 3, 6, 2, 7, 5

Rount 6
=> 1, 4
=> -
=> return => 3, 6, 2, 7, 5, 1

Rount 7
=> 4
=> -
=> return => 3, 6, 2, 7, 5, 1, 4


Rount 8
=> Empty
=>
=> return => 3, 6, 2, 7, 5, 1, 4

접근법

이 문제는 2가지 방법으로 해결할 수 있다.

1. 연결 리스트
2. 큐 자료구조

연결 리스트로 해결

사실 이 문제는 연결 리스트로 해결하기보다, 큐로 해결하는 것이 훨씬 더 편하다.

 

그 이유는 연결 리스트로 우리는 큐와 비슷한 동작을 하게 만들 것이기 때문이다.

 

우선 n이 들어오면 n길이를 갖는 정답 배열을 만들고, k번째 수는 1 ~ n 까지 배열을 k번 돌며 0번째 인덱스에 있는 리스트 노드의 값을 출력하도록 한다.

 

이 과정을 n번 반복하면 우리가 원하는 요세푸스 수열이 탄생하게 되는 것이다.

private static int[] solveByLinkedList(int n, int k) {

  List<Integer> list = new LinkedList<>();
  int[] answer = new int[n];
  k -= 1; // k 인덱스를 구하기 위해 -1
  for (int i = 0; i < n; i++) {
    list.add(i + 1); // 1 ~ n 으로 구성된 수열 초기화
  }

  for (int i = 0; i < n; i++) {
    int loop = k; // k만큼 반복을 위해 반복 변수 설정
    while(loop-- > 0) {
      list.add(list.remove(0)); // k번째가 아닌 수들을 다시 리스트 끝으로 이동
    }
    answer[i] = list.remove(0); // k번째 수는 정답 배열에 추가
  }
  return answer;
}

큐 자료구조로 해결

큐로 해결하는 논리는 위의 연결 리스트로 해결하려는 논리와 같다.

하지만 다른점이 하나 있다면, 자료 구조만 달라졌다는 것이다.

private static int[] solveByQueue(int n, int k) {
  Queue<Integer> queue = new LinkedList<>();
  int[] answer = new int[n];
  for (int i = 0; i < n; i++) {
    queue.add(i + 1);
  }
  int index = 0;
  while(!queue.isEmpty()) {
    for (int i = 0; i < k-1; i++) {
        int value = queue.remove();
        queue.add(value);
    }
    answer[index] = queue.remove();
    index++;
  }
  return answer;
}

오답 후보

정답 코드

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);
        int[] answer = solveByQueue(n, k);


        if(n == 1 && k == 1) {
            bw.write("<" + answer[0] + ">");
        }else {
            bw.write("<" + answer[0]);
            for (int i = 1; i < answer.length - 1; i++) {
                bw.write(", " + answer[i]);
            }
            bw.write(", " + answer[answer.length-1] + ">");
        }

        bw.flush();
        bw.close();
    }

    private static int[] solveByLinkedList(int n, int k) {

        List<Integer> list = new LinkedList<>();
        int[] answer = new int[n];
        k -= 1;
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }

        for (int i = 0; i < n; i++) {
            int loop = k;
            while(loop-- > 0) {
                list.add(list.remove(0));
            }
            answer[i] = list.remove(0);
        }
        return answer;
    }
    private static int[] solveByQueue(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            queue.add(i + 1);
        }
        int index = 0;
        while(!queue.isEmpty()) {
            for (int i = 0; i < k-1; i++) {
                int value = queue.remove();
                queue.add(value);
            }
            answer[index] = queue.remove();
            index++;
        }
        return answer;
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

두 풀이 방법 모두 통과하는 것을 볼 수 있다.