TIL. 큐 알고리즘 문제풀이

큐 (Queue)

큐(Queue)는 컴퓨터 과학에서 매우 중요한 자료구조 중 하나이다. 큐는 FIFO(First In, First Out) 원칙을 따르는 선형 자료구조로, 첫 번째로 추가된 요소가 첫 번째로 제거된다.
이는 실생활에서 사람들이 줄을 서는 것과 유사하며, 이러한 특성 때문에 다양한 컴퓨터 과학 분야 및 애플리케이션에서 널리 사용된다.

큐의 사용 사례

큐는 다양한 알고리즘과 시스템에서 사용된다.

• 작업 스케줄링: 운영 체제에서 프로세스 또는 스레드의 실행 순서를 관리하기 위해 큐를 사용할 수 있다. 이는 시스템 리소스에 대한 접근 순서를 결정하는 데 도움이 된다.

• 네트워크 요청 처리: 웹 서버는 동시에 많은 요청을 받을 수 있으며, 이러한 요청을 순서대로 처리하기 위해 큐를 사용할 수 있다.

• 데이터 스트림 처리: 실시간 데이터 스트림(예: 로그 파일, 주식 시세 등)을 처리할 때, 데이터 항목을 순서대로 처리하기 위해 큐를 사용한다.

• 이벤트 관리: GUI(Graphical User Interface) 프로그래밍에서 사용자 이벤트(예: 마우스 클릭, 키보드 입력)를 관리하기 위해 이벤트 큐를 사용한다.

큐 방식의 알고리즘 예시

👉 요세푸스 문제: 큐를 사용하여 풀 수 있는 고전적인 예제.

N명의 사람이 원을 이루어 앉아 있고, K번째 사람을 순차적으로 제거해 나가며, 마지막으로 남는 사람을 찾는 문제이다. 이 문제를 큐를 사용하여 풀 때, 사람들을 큐에 넣고 K번째 사람을 큐에서 제거(Dequeue)한 다음, 다시 큐의 뒤로 추가(Enqueue)한다. 이 과정을 마지막 한 사람이 남을 때까지 반복한다.

✍️ 큐는 이처럼 순서가 중요한 상황에서 요소들을 관리할 필요가 있을 때 유용하게 사용된다.
JavaScript에서 배열의 push() 와 shift() 메서드를 사용하여 간단히 큐를 구현할 수 있다.🧐

1. 공주 구하기

문제 설명

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 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)가 주어진다.

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

▣ 입출력 예

input	output
8 3	7

풀이

const 요세푸스_서바이벌 = (n, k) => {
let arr = Array(n).fill().map((_, i) => i + 1); // 배열초기화 방법1

  while (arr.length > 1) {
    for (let i = 1; i <= k; i++) {
      let current = arr.shift();
      arr.push(current);

      if (i === k) {
        arr.pop();
      }
    }
  }
  return arr[0];
};

let numPeople = 8;
let skipCount = 3;
console.log(요세푸스_서바이벌(numPeople, skipCount));

👉 큐 배열을 만들어서 풀어보자.

• 1) Array(), fill(), map()을 이용해 원하는 길이의 arr를 만든다.
• 2) while문을 통해 arr.length길이가 1이 될때까지 돌린다.
• 2-1) 내부적으로는 for문을 통해 arr의 길이를 줄여나간다.
• 3) i를 k만큼 돌리는 것을 반복한다. 이때 가장 처음 요소를 맨 뒤로 옮긴다.
• 3-1) for문을 반복하다가 if문을 통해 k번째 요소에서는 다시 요소의 맨끝을 pop하여 제거한다.

📌 배열초기화 방법 1)
Array(n).fill().map((_, i) => i + 1)
이 방법은 먼저 Array(n)으로 크기가 n인 배열을 만들고, fill() 메서드로 모든 요소를 undefined로 초기화한 다음, map() 메서드를 사용하여 각 요소를 원하는 값으로 변환한다.
장점: 여러 단계를 거쳐 초기화하므로, 변환 과정을 조금 더 세분화하여 표현할 수 있다.
단점: 코드가 다소 길어지며, fill()과 map()을 연쇄적으로 사용함으로써 발생하는 성능 상의 미세한 오버헤드가 있을 수 있으며, 이해하기 다소 복잡할 수 있다.

🧐 조금 더 간단하게 수정하면...

const 요세푸스_서바이벌2 = (n, k) => {
  let arr = Array.from({ length: n }, (_, i) => i + 1);

  while (arr.length > 1) {
    for (let i = 1; i <= k; i++) {
      arr.push(arr.shift());
    }
    arr.pop();
  }
  return arr[0];
};

let numPeople2 = 8;
let skipCount2 = 3;
console.log(요세푸스_서바이벌2(numPeople2, skipCount2));

• 기존 배열초기화 방법대신 ES6에서 도입된 Array.from 을 이용한다.
• current라는 변수를 따로선언하지 않고 push 코드에서 한번에 shift()처리한다.
• if문을 둘 필요없다. for문에서 i조건에 의해 한 번씩 순회하게 되고, 한 번을 다 순회하는 지점이 pop()을 해주는 지점(if문)과 일치하므로 생략한다.

📌 배열초기화 방법 2)
Array.from({ length: n }, (_, i) => i + 1)
여기서의 Array.from() 메서드는 주어진 길이(length)의 배열을 만들고, 두 번째 인자로 주어진 함수를 사용하여 배열의 각 요소를 초기화한다.
장점: 한 줄로 간결하게 배열을 초기화하고 값을 할당할 수 있다. Array.from()의 사용 의도가 명확하게 드러나므로 가독성이 좋다.

👉 Array.from()과 length 속성 사용 예

Array.from()을 사용하여 길이가 주어진 배열을 생성하는 방법

let arr = Array.from({ length: 5 }, (_, i) => i);
console.log(arr); // [0, 1, 2, 3, 4]

✍️ solution

function solution(n, k) {
        let answer;
        let queue = Array.from({ length: n }, (v, i) => i + 1);
        while (queue.length) {
          for (let i = 1; i < k; i++) queue.push(queue.shift());
          queue.shift();
          if (queue.length === 1) answer = queue.shift();
        }
        return answer;
      }

      console.log(solution(8, 3));

2. 교육과정 설계

문제 설명

현수는 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“를 출력합니다.

▣ 입출력 예

input	output
CBA, CBDAGE	YES

풀이

const Curriculum = (필수, 계획) => {
  let needQ = [...필수];
  let planQ = [...계획];

  for (let plan of planQ) {
    if (needQ.indexOf(plan) !== -1) {
      if (plan !== needQ.shift()) return 'NO';
    }
  }
  if (needQ.length > 0) return 'NO';
  return 'YES';
};

console.log(Curriculum('CBA', 'CBDAGE')); // 'YES'
console.log(Curriculum('CBA', 'CGEADB')); // 'NO'

👉 각각 큐 배열을 만들어서 풀어보자.

• 1) 계획을 배열로 만든다. (큐 배열)
• 1-2) 필수를 배열로 만든다. (큐 배열)
• 2) 큐 배열을 앞에서부터 하나씩 shift() 하고, shift()된 값을 임의의 변수(plan)에 저장한다.
• 3) 조건문을 통해 필수 배열에 만약 shift()된 값이 있다면(indexOf이용) 조건문 안으로 들어가고, 없다면 무시한다.
• 4) 조건문안에서 계획 큐배열의 shift()된 값과, 필수 큐배열의 shift()된 값이 일치하면 넘어가고 불일치하면 'NO'를 반환한다.
• 5) 필수배열의 길이가 0이되면 'YES'를 반환한다.

🧐 조금더 간단하게 수정하면...

const Curriculum = (필수, plan) => {
  let needQ = [...필수];

  for (let curPlan of plan) {
    if (needQ.includes(curPlan)) {
      if (curPlan !== needQ.shift()) return 'NO';
    }
  }
  if (needQ.length > 0) return 'NO';
  return 'YES';
};

console.log(Curriculum('CBA', 'CBDAGE')); // 'YES'
console.log(Curriculum('CBA', 'CGEADB')); // 'NO'

• 굳이 두개의 큐 배열을 만들 필요가 없다.😀

✍️ NOTE
직접 문자열 plan을 for...of 루프로 순회하는 방식으로 변경한 것은 JavaScript에서 문자열도 이터러블(iterable) 객체이기 때문에 가능하다.
이터러블 객체는 for...of 루프를 사용하여 그 요소들을 순회할 수 있다. 따라서 문자열의 경우, 이터러블 객체로서 각 문자(character)를 순회할 수 있다.

첫 번째 코드에서는 계획 문자열을 먼저 배열로 변환한 후 [...계획] 그 배열을 순회했다. 이 방식은 문자열의 각 문자를 배열의 요소로 만들고, 배열을 순회하는데, 이것은 문자열을 배열로 변환하는 추가적인 단계를 포함한다.

두 번째 코드에서는 이러한 변환 과정 없이 바로 문자열 계획을 순회한다. 각 순회에서 curPlan 변수에는 plan 문자열의 각 문자가 차례대로 할당된다. 이 방법은 더 직관적이고 효율적일 수 있으며, 문자열의 각 문자를 배열로 변환하는 과정을 생략하여 불필요한 메모리 사용과 처리 시간을 줄일 수 있다. 👍

✍️ solution

function solution(need, plan) {
  let answer = 'YES';
  let queue = need.split('');
  for (let x of plan) {
    if (queue.includes(x)) {
      if (x !== queue.shift()) return 'NO';
    }
  }
  if (queue.length > 0) return 'NO';
  return answer;
}

let a = 'CBA';
let b = 'CBDAGE';
console.log(solution(a, b));