[문제풀이] 05-06. 공주 구하기

인프런, 자바(Java) 알고리즘 문제풀이

Stack, Queue(자료구조) - 0506. 공주 구하기

🗒️ 문제

🎈 나의 풀이

	private static int solution(int n, int m) {
        Queue<Integer> Q = new LinkedList<>();

        for(int i=0; i<n; i++) Q.add(i);

        while(Q.size() != 1) {
            for(int i=0; i<m; i++) {
                if(i<m-1) Q.add(Q.poll());
                else Q.remove();
            }
        }

        return Q.poll() + 1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(solution(n, m));
    }

🖍️ 강의 풀이

    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;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int k=kb.nextInt();
		System.out.println(T.solution(n, k));
	}

💬 짚어가기

해당 문제는 Queue를 이용하여 쉽게 풀 수 있다. 큐는 LIFO(Last In First Out)의 특징을
갖는 자료구조로, LinkedList를 통해 생성할 수 있다.

나의 풀이에서는 모든 왕자를 큐에 집어넣고 반복문을 돌며 주어진 번호에 해당하는 순서인 경우 pool,
그렇지 않은 경우 다시 큐에 넣도록 구현하였다.

강의에서는 마찬가지로 모든 왕자를 큐에 집어넣고, 반복문을 돈다. 단, 주어진 번호보다 1 작게 반복하며
왕자들을 꺼냄과 동시에 큐에 다시 집어 넣는다. 그 다음 pool을 한번 수행하도록 구현하였다.