[백준] 프린터 큐 #1966

설명

와 너무너무 어이없게 실수를 해서 거의 2시간 정도 푼 것 같다...
처음에 JS로 풀었고, JS의 1번 풀이와 같이 풀었는데 시간초과 나길래
'아 역시 JS배열은 shift 연산에서 비용이 많이 들어 시간초과가 나는구나'라고 생각했다.
그래서 이전 자료구조 Queue를 사용한 문제에서 Queue class를 정의하는 것을 가져오자 이번에는 메모리 초과 오류가 나길래 이것 저것 수정하며 babel로 트랜스파일링하고 별 짓을 다해봤지만 메모리초과가 해결되지 않아 다른 사람의 Node.js 풀이를 참고했다.

참고했지만 Node.js의 풀이1과 별반 다른게 없어서 속으로 물음표를 띄우고 계속 나의 1번 풀이가 왜 시간초과가 나는지 원인을 찾으려고 별 짓을 또 다했다.

결국 차이를 찾지 못하고 같은 풀이로 c++로 했을때 또 에러가 발생할지 궁금해 c++로 풀었는데 c++로 푸는 와중에 어느 로직을 빠뜨렸다는 것을 찾았다.(20번째 줄의 n -= 1; 코드 한줄...)
이것 때문에 무한 루프가 발생했던 것이였고, 나의 2시간이 사라졌다 ㅋㅋㅋㅠㅠ

Node.js 풀이2를 제출했을 때, 메모리 초과 오류가 아니라 시간 초과 오류였다면 더 빠르게 찾았을 것 같은데...

그래도 덕분에 Node.js 풀이2에서 Queue 클래스에서 전개 연산자를 사용하기 위해 iterator protocol을 추가했고, 거기서 generator 함수를 이용해 구현해본 점이 재미있었고 배울점이 많았다.

class Queue {
  ...
  *[Symbol.iterator]() {
      let cur = this.head;
      while (cur) {
        yield cur.value;
        cur = cur.next;
      }
  }
}

위의 오류를 고치자 일반 배열을 쓴 풀이와 Queue class를 쓴 풀이 모두 통과가 되었고, 이번 문제는 특별히 풀이가 3개가 되었다.(야호...! ㅠㅠ)

Node.js 풀이1

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let N = Number(input[0]);

const solution = (n, m, testcase) => {
  const queue = testcase;
  let isEnd = false;
  let order = 0;
  let cur = m;
  while (!isEnd) {
    const max = Math.max(...queue);
    while (queue[0] !== max) {
      queue.push(queue.shift());
      cur -= 1;
      if (cur < 0) cur += n;
    }
    queue.shift();
    order += 1;
    cur -= 1;
    n -= 1;
    if (cur === -1) {
      isEnd = true;
    }
  }
  return order;
};

let i = 1;
while (N--) {
  const [NM, testcases] = input.slice(i, i + 2);
  const [n, m] = NM.split(' ').map(Number);
  const testcase = testcases.split(' ').map(Number);
  i += 2;
  console.log(solution(n, m, testcase));
}

Node.js 풀이2

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let N = Number(input[0]);

class Node {
  prev = null;
  next = null;
  constructor(value) {
    this.value = value;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) this.head = newNode;
    if (this.tail) {
      this.tail.next = newNode;
      newNode.prev = this.tail;
    }
    this.tail = newNode;
    this.length += 1;
  }
  pop() {
    if (this.length === 0) return -1;
    const value = this.head.value;
    this.head = this.head.next;
    this.length -= 1;
    return value;
  }
  front() {
    return this.length ? this.head.value : -1;
  }
  *[Symbol.iterator]() {
    let cur = this.head;
    while (cur) {
      yield cur.value;
      cur = cur.next;
    }
  }
}

const solution = (n, cur, testcase) => {
  const queue = new Queue();
  for (const v of testcase) queue.push(v);
  let order = 0;
  while (true) {
    const max = Math.max(...queue);
    while (queue.front() !== max) {
      queue.push(queue.pop());
      cur -= 1;
      if (cur < 0) cur += n;
    }
    queue.pop();
    order += 1;
    cur -= 1;
    n -= 1;
    if (cur === -1) break;
  }
  return order;
};

let i = 1;
while (N--) {
  const [NM, testcases] = input.slice(i, i + 2);
  const [n, m] = NM.split(' ').map(Number);
  const testcase = testcases.split(' ').map(Number);
  i += 2;
  console.log(solution(n, m, testcase));
}

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    
    while(N--) {
        deque<int> DQ;
        int n, m;
        cin >> n >> m;
        for (int i=0; i<n; i++) {
            int v; cin >> v;
            DQ.push_back(v);
        }
        int cur = m;
        int order = 0;
        while (true) {
            int max = *max_element(DQ.begin(), DQ.end());
            while(DQ.front() != max) {
                DQ.push_back(DQ.front()); DQ.pop_front();
                cur -= 1;
                if (cur < 0) cur += n;
            }
            DQ.pop_front();
            order += 1;
            cur -= 1;
            n -= 1;
            if (cur == -1) break;
        }
        cout << order << '\n';
        
    }
    
    return 0;
}