[Algorithm] Queue

이번 장에서는 Queue를 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.

---

공주 구하기

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 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
  83
• 출력예제 1
  7

public class RescuePrincess {

    public int solution1(int princes, int count) {
        int answer = 0;
        Queue<Integer> queueOfPrince = new LinkedList<>();
        for (int i = 1; i <= princes; i++) {
            queueOfPrince.offer(i);
        }
        while (!queueOfPrince.isEmpty()) {
            for (int i = 1; i < count; i++) {
                queueOfPrince.offer(queueOfPrince.poll());
            }
            queueOfPrince.poll();
            if (queueOfPrince.size() == 1) {
                answer = queueOfPrince.poll();
            }
        }
        return answer;
    }

    @Test
    @DisplayName("공주 구하기")
    public void main() {
        int expectedAnswer = 7;
        int answer1 = solution1(8, 3);
        assertEquals(expectedAnswer, answer1);
    }

}

---

교육과정 설계

현수는 1년 과정의 수업계획을 짜야 합니다.
수업중에는 필수과목이 있습니다. 이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있습니다.
만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어지면 필수과목은 C, B, A과목이며 이 순서대로 꼭 수업계획을 짜야 합니다.
여기서 순서란 B과목은 C과목을 이수한 후에 들어야 하고, A과목은 C와 B를 이수한 후에 들어야 한다는 것입니다.
현수가 C, B, D, A, G, E로 수업계획을 짜면 제대로 된 설계이지만 C, G, E, A, D, B 순서로 짰다면 잘못 설계된 수업계획이 됩니다.
수업계획은 그 순서대로 앞에 수업이 이수되면 다음 수업을 시작하다는 것으로 해석합니다. 수업계획서상의 각 과목은 무조건 이수된다고 가정합니다.
필수과목순서가 주어지면 현수가 짠 N개의 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력하는 프로그램을 작성하세요.

• 입력설명
  첫 줄에 한 줄에 필수과목의 순서가 주어집니다. 모든 과목은 영문 대문자입니다. 두번째 줄부터 현수가 짠 수업설계가 주어집니다.(수업설계의 길이는 30이하이다)
• 출력설명
  첫 줄에 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력합니다.
• 입력예제 1
  CBA
  CBDAGE
• 출력예제 1
  YES

public class CurriculumDesign {

    public String solution1(String essential, String clazz) {
        Queue<Character> queueOfEssential = new LinkedList<>();
        for (char c : essential.toCharArray()) {
            queueOfEssential.add(c);
        }
        for (char c : clazz.toCharArray()) {
            if (queueOfEssential.contains(c)) {
                if (queueOfEssential.poll() != c) {
                    return "NO";
                }
            }
        }
        return queueOfEssential.isEmpty() ? "YES" : "NO";
    }

    @Test
    @DisplayName("교육과정 설계")
    public void main() {
        String essential = "CBA";
        String clazz = "CBDAGE";
        String expectedAnswer = "YES";
        String answer1 = solution1(essential, clazz);
        assertEquals(expectedAnswer, answer1);
    }

}

---

응급실

메디컬 병원 응급실에는 의사가 한 명밖에 없습니다.
응급실은 환자가 도착한 순서대로 진료를 합니다. 하지만 위험도가 높은 환자는 빨리 응급조치를 의사가 해야 합니다.
이런 문제를 보완하기 위해 응급실은 다음과 같은 방법으로 환자의 진료순서를 정합니다.
• 환자가 접수한 순서대로의 목록에서 제일 앞에 있는 환자목록을 꺼냅니다.
• 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣습니다. 그렇지 않으면 진료를 받습니다.
즉 대기목록에 자기 보다 위험도가 높은 환자가 없을 때 자신이 진료를 받는 구조입니다.
현재 N명의 환자가 대기목록에 있습니다.
N명의 대기목록 순서의 환자 위험도가 주어지면, 대기목록상의 M번째 환자는 몇 번째로 진료를 받는지 출력하는 프로그램을 작성하세요.
대기목록상의 M번째는 대기목록의 제일 처음 환자를 0번째로 간주하여 표현한 것입니다.

• 입력설명
  첫 줄에 자연수 N(5<=N<=100)과 M(0<=M<N) 주어집니다.
  두 번째 줄에 접수한 순서대로 환자의 위험도(50<=위험도<=100)가 주어집니다.
  위험도는 값이 높을 수록 더 위험하다는 뜻입니다. 같은 값의 위험도가 존재할 수 있습니다.
• 출력설명
  M번째 환자의 몇 번째로 진료받는지 출력하세요.
• 입력예제 1
  52
  60 50 70 80 90
• 출력예제 1
  3
• 입력예제 2
  63
  70 60 90 60 60 60
• 출력예제 2
  4

public class EmergencyRoom {

    @AllArgsConstructor
    static class Patient {
        int number;
        int emergency;
    }

    public int solution1(int patients, int target, int[] emergencies) {
        int answer = 0;
        Queue<Patient> queueOfPatients = new LinkedList<>();
        for (int i = 0; i < emergencies.length; i++) {
            queueOfPatients.offer(new Patient(i, emergencies[i]));
        }

        while (!queueOfPatients.isEmpty()) {
            Patient tmp = queueOfPatients.poll();
            for (Patient p : queueOfPatients) {
                if (p.emergency > tmp.emergency) {
                    queueOfPatients.offer(tmp);
                    tmp = null;
                    break;
                }
            }
            if (Objects.nonNull(tmp)) {
                answer++;
                if (tmp.number == target) {
                    return answer;
                }
            }
        }
        return answer;
    }

    @Test
    @DisplayName("응급실")
    public void main() {
        int expectedAnswer1 = 3;
        int answer1 = solution1(5, 2, new int[]{60, 50, 70, 80, 90});
        assertEquals(expectedAnswer1, answer1);

        int expectedAnswer2 = 4;
        int answer2 = solution1(6, 3, new int[]{70, 60, 90, 60, 60, 60});
        assertEquals(expectedAnswer2, answer2);
    }

}

---

참고한 강의: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84