프로그래머스 [프린터]

자료구조 큐를 이용한 풀이

• 선형 자료구조인 큐를 이용하여 해결 가능한 문제이다.

내가 작성한 코드

function solution(priorities, location) {
    // 인쇄되는 횟수 측정 변수
    let count = 0
    // 인쇄를 원하는 대기목록의 요소(동일한 요소들이 있어 구별해내기 위해 문자열로 형변환)
    priorities[location] = priorities[location] + ''
    
    while(1) {
        if(Number(priorities[0]) === Math.max(...priorities)) {
            count++
            if(typeof priorities[0] === 'string') {
                break;
            }
            priorities.shift()
        }
        else {
            let notPrint = priorities[0]
            priorities.shift()
            priorities.push(notPrint)
        }
    }
    return count
}

위 코드를 간단하게 요약하자면

• 인쇄를 원하는 문서의 위치를 기억하기 위해 다른 요소들이 숫자형인 것과 다르게 문자형으로 변환해준다.
• while loop을 이용하여 큐의 맨 앞에 중요도가 가장 높은 문서가 먼저 오도록 shift와 push를 반복한다. 이때 중요도가 가장 높은 문서가 큐의 맨 앞에 오면, count를 하나 증가시켜주고 shift한다.
• 인쇄를 원하는 문서가 큐의 맨 앞에 등장하면, count를 하나 증가시켜주고 반복문을 중단한다.
• count를 반환한다.

개선할 사항

• 다른 사람들의 풀이를 참고해보니, map 함수를 이용하여 인덱스와 요소를 재지정해주고, some 함수, 그리고 findIndex를 이용하여 푸는 방법을 이용하니 깔끔해보였다.
• 원하는 문서의 위치를 얻기 위해 문자열로 형변환하는 것보다 map 함수를 이용하여 인덱스를 이용하는 것이 더 적절해보인다고 생각한다. 추후에 다시 풀이를 시도해보겠다.

개선한 풀이

function solution(priorities, location) {
    const arr = priorities.map((item, index) =>
          ({priority:item, index}))
    
    const queue = []
    
    while(arr.length > 0) {
        const headPriority = arr.shift()
        const isHighPriority = arr.some(el => el.priority > headPriority.priority)
        if(isHighPriority) {
            arr.push(headPriority)
        }
        else {
            queue.push(headPriority)
        }
    }
    return queue.findIndex(el => el.index === location) + 1
}

• map 함수를 이용하여 각 요소가 우선순위와 인덱스 정보를 담고 있는 객체 형태가 되게끔 생성한다.
  • 인쇄를 원하는 문서의 위치를 기억하기 위해서이다.
• 인쇄가 완료된 문서를 담을 큐 queue를 선언한다.
• 맨 앞 요소를 먼저 뽑고, some 함수를 이용하여 뽑은 요소보다 큰 요소가 하나라도 있는지 검사한다.
  • some 함수는 배열 내 모든 요소에 대해 조건이 일치하는 것이 하나라도 있으면 그 즉시 true를 반환한다.
• 만약 하나라도 맨 앞 요소보다 크다면, 뽑은 요소를 다시 오른쪽에서 push한다.
• 그렇지 않다면 해당 요소는 인쇄가 가능하게 되므로 queue에 push한다.
• 문서가 몇 번째로 인쇄되었는지 찾기 위해 findIndex 함수를 이용하고, 해당 값은 인덱스 값이기 때문에 + 1 해준다.
  • 지금까지 findIndex 함수는 단순히 일치하는 값을 찾는 함수인줄 알았다.
  • findIndex 내 판별 함수를 이용하는 것이 가능하다는 것을 배웠다!

큐

• 배열로 큐 구현하기

class Queue {
  constructor() {
	this.queue = [];
    this.front = 0;
    this.rear = 0;
}

enqueue(value) {
	this.queue[this.rear++] = value;
}

dequeue() {
	const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
}

peek() {
	return this.queue[this.front];
}

size() {
	return this.rear - this.front;
}
}

• 연결 리스트로 큐 구현하기

class Node {
	constructor(value){
    	this.value = value;
        this.next = null;
    }
}

class Queue {
	constructor() {
    	this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    enqueue(newValue) {
    	const newNode = new Node(newValue);
        if (this.head === null) {
        	this.head = this.tail = newNode;
        } else {
        	this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size += 1;
    }
    
    dequeue() {
    	const value = this.head.value;
        this.head = this.head.next;
        this.size -= 1;
        return value;
    }
    
    peek() {
    	return this.head.value;
    }
}