여러상황에서 Queue 학습하기

Practice1 카드섞기

import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;

public class Practice1 {
    public static int findLastCard(int N) {
        Queue queue = new LinkedList();

        IntStream.range(1, N + 1).forEach(x -> queue.add(x));
        System.out.println(queue);

        while (queue.size() > 1) {
            queue.remove();
            int data = (int)queue.remove();
            queue.add(data);
            System.out.println(queue);
        }
        return (int)queue.remove();
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(findLastCard(4));    // 4
        System.out.println(findLastCard(7));    // 6
        System.out.println(findLastCard(9));    // 2
    }
}

findLastCard 메서드

public static int findLastCard(int N) {
	Queue<Integer> queue = new LinkedList<>();

-주어진 N에 대해 마지막 남은 카드 찾는 메서드
-queue는 LinkedList 를 사용하여 구현된 Queue

1. queue 초기화

IntStream.range(1, N + 1).forEach(x -> queue.add(x));
System.out.println(queue);

-IntStream.range(1, N + 1) : 1부터 N까지의 정수 스트림을 생성
-forEach(x -> queue.add(x)) : 각 정수를 queue에 추가
-초기상태의 queue를 출력

2. queue 처리

while (queue.size() > 1) {
	queue.remove();
    int data = queue.remove();
    queue.add(data);
    System.out.println(queue);
}

-while (queue.size() > 1) : queue의 크기가 1보다 큰 동안 반복
-queue.remove() : queue의 첫번째 요소를 제거 (버려진 카드)
-int data = queue.remove() : 다음 카드를 제거하고 data에 저장
-queue.add(data) : data를 queue의 끝에 추가 (카드를 queue의 맨 뒤로 옮김)
-현재상태의 queue를 출력

3. 마지막 남은 카드 반환

return queue.remove();

-queue에 남아있는 유일한 요소를 제거하고 반환

Practice2 요세푸스 순열 문제

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;

public class Practice2 {

    public static ArrayList getJosephusPermutation(int N, int K) {
        Queue queue = new LinkedList<>();
        ArrayList result = new ArrayList();

        IntStream.range(1, N + 1).forEach(x -> queue.add(x));

        int cnt = 0;
        while (!queue.isEmpty()) {
            int data = (int)queue.remove();
            cnt += 1;

            if (cnt % K == 0) {
                result.add(data);
            } else {
                queue.add(data);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(getJosephusPermutation(5, 2));
        System.out.println(getJosephusPermutation(7, 3));
    }
}

getJosephusPermutation 메서드

public static ArrayList<Integer> getJosephusPermutation(int N, int K) {
	Queue<Integer> queue = new LinkedList<>();
    ArrayList<Integer> result = new ArrayList<>();

-getJosephusPermutation 메서드는 N명의 사람들이 K번째 사람을 제거하는 요세푸스 순열을 계산
-queue 는 LinkedList를 사용하여 구현된 Queue
-result는 최종 순열을 저장할 ArrayList

1. queue 초기화

IntStream.range(1, N + 1).forEach(x -> queue.add(x));

-IntStream.range(1, N + 1) : 1부터 N 까지의 정수 스트림을 생성
-forEach(x -> queue.add(x)) : 각 정수를 queue에 추가

2. 요세푸스 순열 계산

int cnt = 0;
while (!queue.isEmpty()) {
	int data = queue.remove();
    cnt += 1;
    
    if (cnt % K == 0) {
    	result.add(data);
    } else {
    	queue.add(data);
    }
}

-int cnt = 0; : 카운터 변수를 초기화
-while (!queue.isEmpty()) : 큐가 비어있지 않은 동안 반복
-int data = queue.remove() : 큐의 첫번째 요소를 제거하고 data에 저장
-cnt += 1; : 카운터를 증가
-if (cnt % K == 0) : 카운터가 K의 배수인 경우
-result.add(data) : data를 결과 리스트에 추가
-queue.add(data) : 그렇지 않은 경우 data를 큐의 끝에 추가

3. 결과반환

return result;

-최종 요세푸스 순열을 반환