[인프런 알고리즘] Chpater5, 6번 문제(공주 구하기)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int solution(int N, int K) {
        Queue<Integer> que = new LinkedList<>();

        for(int i = 1; i <= N; ++i) que.add(i);

        int count = 0;
        while(que.size() > 1)
        {
            ++count;
            if(count == K)
            {
                que.poll();
                count = 0;
            }
            else que.add(que.poll());
        }
        return que.poll();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, K));
    }
}

 

설명

• 이 문제는 요세푸스 문제라고 불린다.
• count 변수를 초기화하여 사람을 제거할 때까지의 카운트를 유지한다.
• while(que.size() > 1) 루프는 큐에 한 명만 남을 때까지 반복된다.
• ++count;를 통해 카운트를 증가시킨다.
• if(count == K)에서 카운트가 K와 같아지면, que.poll();을 통해 큐의 첫 번째 요소(즉, 현재 사람)를 제거하고, count를 0으로 초기화한다.
• else que.add(que.poll());에서 카운트가 K와 같지 않은 경우, 현재 사람을 큐의 뒤로 이동시킨다. 이때, poll()로 큐의 첫 번째 요소를 제거한 후, 그 요소를 다시 add()로 큐의 끝에 추가한다.

add() 메서드와 offer() 메서드 차이

1. 예외 처리 방식의 차이
-add() 메서드: 큐의 용량 제한을 초과하거나 다른 이유로 요소를 추가할 수 없을 때 IllegalStateException을 던진다. 즉, add()는 요소를 큐에 추가하는 작업이 실패할 경우 예외를 발생시키며, 이를 통해 실패 원인을 알 수 있게 한다.
-offer() 메서드: offer()는 큐의 용량 제한을 초과하거나 다른 이유로 요소를 추가할 수 없을 때 false를 반환한다. 예외를 던지지 않고, boolean 값을 반환하여 추가가 성공했는지 여부를 확인할 수 있다.

2. 메서드 반환 타입
-add(): 반환 타입은 boolean이다. 요소가 정상적으로 추가되면 true를 반환한다. 다만, 이 메서드는 큐가 용량을 초과할 경우 예외를 던지기 때문에, 반환값을 사용하는 경우는 드물다.
-offer(): 반환 타입도 boolean이다. 추가가 성공하면 true, 실패하면 false를 반환한다.

3. 사용 의도
-add(): 주로 큐가 용량 제한이 없거나, 특정 조건에 대해 강력한 에러 처리를 요구하는 경우 사용한다.
-offer(): 주로 큐가 용량 제한이 있거나, 큐가 꽉 찼을 때도 예외를 던지지 않고 부드럽게 실패 처리를 하고자 할 때 사용한다.