[알고리즘] 5-6 공주 구하기 - Queue (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 예습 풀이 코드, 강의 수강 후 복습 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/05-06

예습 풀이

• Queue 자료구조를 사용하여 풀이

package inflearn.stack_queue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//공주 구하기
public class Main5_6 {

    public static int solution(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        int count = 1;

        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }

        while (queue.size() > 1) {
            int num = queue.poll();

            if (count == k) {
                count = 1;
            } else {
                queue.offer(num);
                count++;
            }
        }

        return queue.poll();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        System.out.println(solution(n, k));

        sc.close();
    }
}

강의 풀이

• Queue 자료구조를 사용하여 풀이

public int solution(int n, int k){
    int answer=0;
    Queue<Integer> Q=new LinkedList<>();
    for(int i=1; i<=n; i++) Q.offer(i);

    while(!Q.isEmpty()){
        for(int i=1; i<k; i++) Q.offer(Q.poll());
        Q.poll();
        if(Q.size()==1) answer=Q.poll();
    }
    return answer;
}