[코딩테스트] 큐 문제 1. 요세푸스 문제

개념정리

큐(queue)는 '줄을 서다'라는 뜻을 가지고 있다.

먼저 들어간 데이터가 먼저 나오는 구조이기 때문에, 이를 선입선출 또는 FIFO(First In First Out)이라고 부른다.

 

큐의 기본 동작도 스택과 마찬가지로 삽입 연산을 푸시, 꺼내는 연산을 팝이라고 한다.

 

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환합니다.
연산	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환합니다.
연산	void push(ItemType item)	큐에 데이터를 푸시합니다.
연산	ItemType pop()	큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환합니다.
상태	int front	큐에서 가장 처음에 팝한 위치를 기록합니다.
상태	int rear	큐에서 최근에 푸시한 데이터의 위치를 기록합니다.
상태	ItemType data[maxsize]	큐의 데이터를 관리하는 배열입니다. 최대 maxsize개의 데이터를 관리합니다.

 

 

큐 구현 방법

- shift() 메서드 사용하기

  shift() 메서드는 배열의 가장 첫 번째 요소를 삭제하는 메서드 이기 때문에 push()와 shift() 메서드를 활용하면 큐의 선입선출을 흉내 낼 수 있다. 하지만 shift()메서드의 시간 복잡도는 O(1)이 아니기 때문에 진짜 큐는 아니다.

 

- 배열을 이용하는 방식

class Queue {
 items = [];
 front = 0;
 rear = 0;
 
 push(item) {
  this.items.push(item);
  this.rear++;
 }

 pop() {
  return this.items[this.front++];
 }
 
 isEmpty() {
  teturn this.front === this.rear;
 }
}

※ 이 방식이 편하긴 하지만, 배열 메모리가 계속해서 증가함을 알 수 있다.

 

- 연결 리스트를 이용하는 방식

class Node {
  constructor(data) {
    this.data = data; // 요소의 값
    this.next = null; // 다음 요소를 참조
  }
}

class Queue {
  constructor() {
    this.head = null; // 첫 번째 요소 참조
    this.tail = null; // 마지막 요소 참조
    this.size = 0; // 큐의 길이
  }

  push(data) {
    // 새로운 요소를 생성
    const newNode = new Node(data);

    if (!this.head) { // 큐가 비어 있다면 head와 tail을 모두 새로 생성한 요소로 설정
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 아니면 현재 tail의 next 속성을 새로운 요소로 설정 후 tail이 새로운 요소를 참조하도록 변경
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++; // 큐 길이 증가
  }

  pop() {
    // head가 null이라면 비어 있다는 뜻
    if (!this.head) {
      return null;
    }

    // 두 번째 요소를 head의 참조로 변경하면 자연스럽게 첫 번째 요소가 사라짐
    const removeNode = this.head;
    this.head = this.head.next;

    // 만약 두 번째 요소가 없었다면
    // 큐가 비어 있다는 뜻이니 tail도 null로 설정
    if (!this.head) {
      this.tail = null;
    }

    this.size--; // 큐 길이 감소

    // 삭제된 요소의 값을 반환
    return removeNode.data;
  }

  isEmpty() {
    return this.size === 0;
  }
}

 

큐 문제 1. 요세푸스 문제

문제 설명

N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.
 - 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.
 - 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.
N과 K가 주어질 때 마지막 살아있는 사람의 번호를 반환하는 solution() 함수를 구현해 주세요.

제약 조건
- N과 K는 1이상 1000이하의 자연수입니다.

입출력의 예

N	K	return
5	2	3

 

정답

class Queue {
  items = [];
  front = 0;
  rear = 0;

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  // 이 문제에서는 큐의 크기를 알아야 합니다
  size() {
    return this.rear - this.front;
  }

  pop() {
    return this.items[this.front++];
  }
}

function solution(N, K) {
  const queue = new Queue();

  // ❶ 1부터 N까지의 번호를 deque에 추가
  for (let i = 1; i <= N; i++) {
    queue.push(i);
  }

  while (queue.size() > 1) {
    // ❷ deque에 하나의 요소가 남을 때까지
    for (let i = 0; i < K - 1; i++) {
      queue.push(queue.pop()); // ❸ K번째 요소를 찾기 위해 앞에서부터 제거하고 뒤에 추가
    }
    queue.pop(); // ❹ K번째 요소 제거
  }

  return queue.pop(); // ❺ 마지막으로 남은 요소 반환
}

console.log(solution(5, 2)); // 3