카드2[2164] - 백준
문제 링크
https://www.acmicpc.net/problem/2164
풀이
처음에는 단순히 JS에 존재하는 shift와 push 메서드를 사용하여 풀었지만, 시간 초과로 인해 직접 큐를 구현하게 되었다.
여기서 구현한 큐는 링크드 리스트를 기반으로 구현하였다.
링크드 리스트를 기반으로 한 큐 구현
우선, 각 노드는 value, next, prev 값을 가지고 있다.
Queue는 각 노드들의 묶음이며, 링크드 리스트 형식으로 되어있다.
또한, 노드의 삭제, 추가를 위해 head와 tail이 존재한다.
-
push() 구현
queue에 3의 값을 push() 하고자 할 때,
push할 노드의 prev와 기존 tail 위치의 노드를 엮어주고,
기존 tail 위치의 next와 push할 노드를 엮어준다.
마지막으로, tail값을 새로 push하는 노드로 바꿔주면 된다.
-
shift() 구현
queue에 있는 첫 번째 값인 1을 shift() 하려고 할 때,
첫 번째 노드에 있던 head를 head.next에 있는 노드(2)로 옮긴다.
이후, head.prev의 값을 null로 변경하면 된다.
전체 코드
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input.shift())
class Node{
constructor(value){
this.value=value;
this.next = null;
this.prev = null;
}
}
class Queue{
constructor(){
this.head=null;
this.tail=null;
this.size=0;
}
shift(){
this.head = this.head.next;
this.head.prev=null;
this.size=this.size-1;
}
push(value){
const newNode = new Node(value);
if(!this.head){
this.head = newNode;
}else{
this.tail.next = newNode;
newNode.prev = this.tail;
}
this.tail = newNode;
this.size = this.size+1;
return newNode
}
getHead(){
return this.head.value
}
getSize(){
return this.size;
}
}
const queue = new Queue();
for(let i=1;i<=N;i++){
queue.push(i)
}
while(queue.getSize()!==1){
queue.shift();
queue.push(queue.getHead());
queue.shift();
}
console.log(queue.getHead())프린터 - 프로그래머스
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42587
풀이
queue와 sequence 배열을 만든다.
queue는 priorities로 들어오는 값들을 가지고 있는 배열이고,
sequence는 이런 queue의 순서를 담당하는 배열이다.
Math.max()를 통해 맨 앞을 제외한 나머지 배열의 최대값을 구하고, 이를 맨 앞 값과 비교한다.
- 맨 앞 값이 가장 클 때, queue와 sequence의 첫 번째 값을 shift()를 통해 내보내며 count를 1증가시킨다.
=> 이때, sequence의 맨 앞의 값이 location과 같다면 count를 리턴한다. - 맨 앞 값보다 큰 값이 뒤에 있을 때, queue와 sequence의 첫 번째 값을 맨 뒤로 보낸다.
전체 코드
function solution(priorities, location) {
let queue = priorities;
let sequence = new Array(priorities.length).fill(0).map((_, i) => i);
let count=0;
while(true){
if(Math.max(...queue.slice(1))>queue[0]){
queue.push(queue.shift())
sequence.push(sequence.shift())
}
else{
count++;
queue.shift()
if(sequence.shift()===location){
return count
}
}
//console.log(queue,sequence)
}
return count
}캐시 - 프로그래머스
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/17680#
풀이
캐시에 어떤 정보를 저장시키고자 할 때, 캐시에 해당 정보가 없으면 cache miss가 되며, cache 에 해당 정보가 저장된다.
만약, 캐시에 해당 정보가 있다면 cache hit가 되며, cache에 해당 정보가 저장된다.
여기서 정보를 저장하는 순서는 LRU(Least Recently Used)를 따라, 같은 정보더라도 최근의 정보를 캐시의 젤 위에 push한다.(기존 정보는 delete)
캐시는 자신의 사이즈를 넘어설 때마다, 가장 아래 있는 정보를 shift한다.
전체 코드
function solution(cacheSize, cities) {
var answer = 0;
let cache = [];
if(cacheSize===0) return cities.length*5
cities.map((city)=>{
let regularized_city = city.toLowerCase()
if(cache.includes(regularized_city)){
cache.splice(cache.indexOf(regularized_city),1)
cache.push(regularized_city)
answer++; //cache hit
}else{
if(cache.length>=cacheSize){
cache.shift()
}
cache.push(regularized_city)
answer=answer+5; //cache miss
}
})
return answer;
}
test