Queue?

FIFO(First-In, First-Out) 자료구조

Queue< DataType > q = new LinkedList<>();
로 선언할 수 있다.

주요 method:
1) .offer(x) : Queue안에 x값을 삽입.
2) .poll() : 가장 맨 앞의 값을 내보내고 return.
3) .contains(x) : Queue안에 x 값이 존재하는지 확인.
4) .peek() : 가장 먼저 들어간값(맨 앞의 값).
ㅡ ㅡ ㅡ ㅡ ㅡ ㅡ ㅡ ㅡ
<- 1 2 3 4 5 6 7 8 < -
ㅡ ㅡ ㅡ ㅡ ㅡ ㅡ ㅡ ㅡ
1~8순서로 값을 넣었을때(offer) 해당 형태로 값이 생성된다.
queue.poll()을 하게되면 1부터 값이 사라진다.
queue.peek() = 1이다.

문제

나의풀이

import java.util.*;

class Main {
	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.size()>1) { // 또는 !q.isEmpty() 
				for(int i=0; i<=k-1;i++) {
					if(i==k-1) q.poll();
					else q.offer(q.poll());
				}
			}
			answer = q.element();
			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));
	}
	
}

다른 풀이

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

풀이방법

1. q의 사이즈가 1이 되면 멈추도록 while문을 걸었다.
   while문 안에서 0~k-1까지도는 for문을 통해
   k-1을 만나면 그냥 poll시키고
   k-1 전의 값을 만나면 다시 queue의 맨 뒤에 넣었다.
   size가 1이되면 자동으로 queue에 남은 왕자번호가 정답이므로 answer 에 담았다.

2. while문을 queue가 비기 전까지 돌렸다.
   그 안에서 1~k까지 for문을 통해
   k 바로 전 까지는 q.offer(q.poll)을 통해 다 queue에 값을 넣어주고, for문이 끝난후 다음값은 k를 불러야할 왕자이므로 그냥 poll()만 시켰다.
   ++
   while문을 끝내기위해, queue의 size가 1일때,
   answer에 poll()하여 값을 저장하고,
   queue가 비워진다.

핵심키워드

if문을 통해 여러 케이스를 다루기보단,
조금만 더 생각해서 쉽게 나타낼수 있는 방법을 고려하자...
그리고 Queue 자료구조를 더 공부하자!