자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 공주 구하기

 

https://hyejin.tistory.com/1236

자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 쇠막대기

-> 이전 문제 풀이 

 

 

 

6. 공주 구하기 

설명

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.

정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다.

정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

 

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다.

그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다.

그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다.

 

한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다.

그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.

이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

 

 

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3을 외쳐 제외된다.

이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7번 왕자에게 공주를 구하러갑니다.

N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.

 

출력

첫 줄에 마지막 남은 왕자의 번호를 출력합니다.

 

예시 입력 1 

8 3

 

예시 출력 1

7

 

 

문제 풀이 1

public int solution(int n, int k)
{
   Queue<Integer> queue = new LinkedList<>();
   
   for (int i = 1; i <= n; i++)
   {
      queue.add(i);
   }
   
   int cnt = 1;
   while (queue.size() != 1)
   {
      if (cnt != k) {
         Integer poll = queue.poll();
         queue.offer(poll);
         cnt++;
      }else {
         queue.poll();
         cnt = 1;
      }
   }
   
   return queue.element();
}

👩‍💻 : 이 문제는 Queue를 이용해서 푸는 문제이다. Queue에 왕자 번호 1 ~ n을 넣어주고, 그 다음 queue의 사이즈가 1이 아닐 때까지 while문으로 반복하면서 k번째 값은 queue에서 빼내고, k번째 값이 아닌 것들은 다시 queue에 집어넣는다. 

이렇게 해서 반복하다가 queue의 사이즈가 1이 되면 마지막 남은 왕자이므로 이 왕자의 값을 꺼내서 리턴해주면 된다. 

cnt 변수를 하나 만들어서 이 값이 k가 되면 k 번째 왕자를 poll 해주고 k 값이 아닐 때는 다시 queue에 offer 해주면 된다. 

(k번째가 되었을 때는 다시 cnt 값을 1로 초기화해주고, k번째가 아닐 때 cnt의 값을 1 증가 시켜줬다.)

 

나는 queue에 값을 넣는 메서드를 몰라서..그냥 add() 와 offer() 메서드가 있길래 이를 활용했고, 

queue에서 값을 꺼낼 때는 poll() 메서드를 사용해서 값을 꺼냈다. 

 

 

 

문제 풀이 2

public int solution2(int n, int k)
{
   int answer = 0;
   Queue<Integer> queue2 = new LinkedList<>();
   for (int i = 1; i <=n; i++)
   {
      queue2.offer(i);
   }
   
   while (!queue2.isEmpty())
   {
      for (int i = 1; i <k; i++)
      {
         queue2.offer(queue2.poll()); // poll() : 꺼내고 그 꺼낸 값을 리턴한다.
      }
      queue2.poll();
      
      if (queue2.size() == 1)
         answer = queue2.poll();
   }
   
   
   return answer;
}

👾 : 강사님도 나와 비슷한 방식으로 풀었는데 강사님은 우선 queue에 offer 메서드를 활용해서 queue에 값을 1 ~ n까지 값을 추가해줬다. 

 

 그 다음 queue가 isEmpty 즉, 비어있지 않을 경우에만 while문을 도는데, 이때 for문을 이용해서 1부터 k 값 전까지는 queue에서 꺼낸 값을 다시 queue에 넣어줬다. (k가 3일 때는 1, 2 두개의 값만 queue에서 꺼내서 queue에 다시 offer 해준다.) 

for문을 돌고 나면 그때가 k번째라는 뜻이기 때문에 queue2에서 poll로 그 값을 꺼내고, 이렇게 반복하다가 queue의 사이즈가 1일 때, 이 값을 꺼내서 answer에 넣어주고, 그러면 queue에 아무것도 들어있지 않기 때문에 while문도 벗어나게 된다. 그리고 answer를 리턴해주면 된다.