[PCCP] 스택 · 큐 · 정렬 · 그리디 알고리즘 [2]

▼ Why ?

이번 문제는 이전 문제에서 사용한 Stack과는 다른 자료구조를 활용해야 할 것 같아 한 번 풀어보았다

---

▼ 공주 구하기

 

문제 정보

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

정보 왕국에는 왕자가 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. 앞에서부터 숫자를 세고 해당 숫자 k를 외치지 않은 경우 데이터를 앞에서 맨 뒤로 옮겨야 하기 때문에, 맨 뒤에 데이터가 삽입(offer)되고, 반대쪽에서 데이터가 삭제(poll)되는 자료구조인 Queue 객체를 생성하는 것이 좋을 것 같다
2. 그리고 외치는 숫자를 체크하기 위해 변수 ' count ' 를 하나 두자

 

해결 코드 0

import java.util.*;

class Solution {
    public int solution(int n, int k){
        Queue<Integer> princeQueue = new LinkedList<>();

        for(int i = 1; i <= n; i++)
            princeQueue.offer(i);

        int count = 1;

        while(princeQueue.size() > 1) {
            if(count % k == 0) {
                princeQueue.poll();
                count++;
                continue;
            }

            princeQueue.offer(princeQueue.poll());
            count++;
        }

        return princeQueue.poll();
    }
}

 

해결 코드 1

• 굳이 외치는 숫자를 체크할 ' count ' 변수를 따로 만들지 않아도 될 것 같아 코드를 수정해보았다

import java.util.*;

class Solution {
    int solution(int n, int k) {
        Queue<Integer> princeQueue = new LinkedList<>();
    
        for(int i = 1; i <= n; i++) {
            princeQueue.add(i);
        }

        while (true) {
            if (princeQueue.size() == 1) break;

            for(int i = 1; i <= k; i++) {
                if (i == k) princeQueue.poll();
                else princeQueue.offer(princeQueue.poll());
            }
        }

        return princeQueue.poll();
    }
}

 

---

▼ 정리

 

• 이번 문제를 통해서 Stack을 활용해야 하는 경우와 Queue를 활용해야 하는 경우를 간단하게 구분해볼 수 있었다
  
  
• 일반적인 배열을 사용했다면 데이터를 삽입하거나 제거할 때마다 index를 수정해줘야 원하는 결과를 얻을 수 있었지만, 그럴 필요없이 Stack이나 Queue 자료구조 형태로 구현하면 쉽게 해결할 수 있다