[JS] 프로그래머스 코딩 테스트 - 기능 개발

📚 문제

기능 개발

📣 풀이

• 시도한 풀이

    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) {
            this.head = newNode;
            this.tail = newNode;
        }
        else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size++;
    }
  
    pop() {
        if (!this.head) return null;
  
        const removeNode = this.head;
        this.head = this.head.next;
  
        if (!this.head) this.tail = null;
  
        this.size--;
  
        return removeNode.data;
    }
  
    isEmpty() {
        return this.size === 0;
    }
  }
  
  function solution(progresses, speeds) {
    let queue = new Queue();
    let answer = [];
  
    for (let i = 0; i < progresses.length; i++) {
        let days = Math.ceil((100 - progresses[i]) / speeds[i]);
        queue.push(days);
    }
  
    while (queue.size > 0) {
        let count = 1;
        let popDays = queue.pop();
  
        while (queue.size > 0 && popDays >= queue.head.data) {
            queue.pop();
            count++;
        }
  
        answer.push(count);
    }
  
    return answer;
  }

💫코드 리뷰 & 반성

[어려웠던 점]
큐로 풀어야 하는 문제인 만큼 큐를 사용하기 위해 노력했다.
맨 처음에는 날짜로 접근해야 하는 아이디어가 안 떠올라서 고생했고
그 다음에는 직접  큐를 구현할 때 주의해야 할 것들 때문에 고생했다.
(아래에 적겠음)

[새롭게 알게된 점]
size === 0도 넣어줘야 하고 newNode 위치나 pop() 등등
length 대신 size라는 것도.
queue.size > 0 && popDays >= queue.head.data
// size가 0보다 큰지 먼저 체크해야 하는 것도.

~큐로 풀었을 때~

~그 전에 배열로 풀었을 때~

아이디어는 비슷한데 shift()로 푼 게 빠르다니 뭔가 자존심이 상함ㅋㅋ
하지만 입력이 아주 커진다면 연결 리스트가 훨씬 빠를 것이다.
100개 정도면 배열로 가는 것도 나쁘지 않겠다.

~책에 있는 코드~
while을 안 쓰고 for문으로 한 번에 쭉 가니까 시간 복잡도 O(N)으로 예쁘게 나옴.

참고

코딩 테스트 합격자 되기 자바스크립트 - 이선협, 박경록 저