선형 자료구조 - 큐(Queue) 연습문제

Practice1

// Practice1
// 카드 섞기
// 1부터 N 까지의 번호로 구성된 N장의 카드가 있다.
// 1번 카드가 가장 위에 그리고 N번 카드는 가장 아래의 상태로 카드가 순서대로 쌓여있다.
// 아래의 동작을 카드 한 장만 남을 때까지 반복했을 때, 가장 마지막 남는 카드 번호를 출력하시오.
// 1. 가장 위의 카드는 버린다.
// 2. 그 다음 위의 카드는 쌓여 있는 카드의 가장 아래에 다시 넣는다.

// 예시 입력)
// N = 4
// 결과: 4

// N = 7
// 결과: 6

 

구현 코드

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));

        while (queue.size() > 1) {
            // 1. 가장 위의 카드는 버린다.
            queue.remove();
            // 2. 그 다음 위의 카드는 쌓여 있는 카드의 가장 아래에 다시 넣는다.
            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
    }
}

 

출력 결과

[3, 4, 2]
[2, 4]
[4]
4
[3, 4, 5, 6, 7, 2]
[5, 6, 7, 2, 4]
[7, 2, 4, 6]
[4, 6, 2]
[2, 6]
[6]
6
[3, 4, 5, 6, 7, 8, 9, 2]
[5, 6, 7, 8, 9, 2, 4]
[7, 8, 9, 2, 4, 6]
[9, 2, 4, 6, 8]
[4, 6, 8, 2]
[8, 2, 6]
[6, 2]
[2]
2

 

---

Practice2

 

// Practice2
// 요세푸스 문제
// N과 K가 주어졌을 때 (N, K) 요세푸스 순열을 구하시오.
// N과 K는 N >= K 를 만족하는 양의 정수이다.
// 1부터 N 번까지 N명이 순서대로 원을 이루어 모여 있다.
// 이 모임에서 원을 따라 순서대로 K번째 사람을 제외한다.
// 모든 사람이 제외될 때까지 반복하며 이 때, 제외되는 순서가 요세푸스 순열이다.

// 예시 입력
// 입력: N = 5, K = 2
// 결과: 2, 4, 1, 5, 3

// 입력: N = 7, K = 3
// 결과: 3, 6, 2, 7, 5, 1, 4

 

구현 코드

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)); //[2, 4, 1, 5, 3]
        System.out.println(getJosephusPermutation(7, 3)); //[3, 6, 2, 7, 5, 1, 4]
    }
}

 

출력 결과

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