https://programmers.co.kr/learn/courses/30/lessons/42628
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 수신 탑(높이)
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
입출력 예
operations return
["I 16","D 1"][0,0]
["I 7","I 5","I -5","D -1"][7,5]
입출력 예 설명
16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.
나의풀이
function solution(operations) {
var queue = []
var index;
operations.map(command => {
var firstLetter = command.split(' ')[0]
var secondLetter = command.split(' ')[1]
if(firstLetter === 'D'){
if(queue.length === 0){
return
}
queue.map(i => Number(i))
if(secondLetter === '1'){
index = queue.indexOf(String(Math.max(...queue)))
queue.splice(index, 1)
}else{
index = queue.indexOf(String(Math.min(...queue)))
queue.splice(index, 1)
}
}else{
queue.push(secondLetter)
}
})
if (queue.length === 0){
return [0,0]
}else{
queue.map(i => Number(i))
return [ Math.max(...queue), Math.min(...queue)]
}
}먼저 문제를 파악했다.
queue안에 operation에서 연산한 결과값을 푸쉬한다.
그리고 queue의 최댓값, 최솟값을 array에 담아 리턴한다.(없을 시에는 [0,0])
operations는 string을 itemd으로 가지는 array이다. string을 띄워쓰기로 split하고(array) 첫번째 item이 "D" 라면 연산을, D가 아니라면 queue에 item[1]을 추가한다.
여기까지는 문제가 없었는데, 1) queue 안의 최솟값과 최댓값을 구하는 문제와 2) 배열 내부의 중복된 숫자중 하나만 지워야하는 문제 가 발생했다.
1) queue안의 최솟값과 최댓값을 구하려면 item이 number여야 하는데, string이였다. 그래서 map을 이용해 item을 Number로 바꾸었다.(더 효율적인 방법이 있을것이다.)
2) array.prototype.filter()를 사용하면 지우고자하는 item을 지울 수 있지만, 중복된 item까지 삭제한다. 문제에서는 중복된 item이 있을 경우 하나만 삭제하라고 했다. 그래서 mdn에서 찾은 array.prototype.indexOf() 함수를 사용했다. 해당함수는 중복된 item이 있어도, 하나의 index만을 return했다. (더 효율적인 방법이 있을것이다.)
2-1) 여기서 indexOf()를 사용하기 위해서는 string을 parameter로 사용해야했는데, 나는 1)에서 Number를 인자로 사용하게 만들었기 때문에, 다시한번 String으로 변환해야했다.(더 효율적인 방법이 있을것이다.)
array.prototype.splice()를 이용해 인덱스에 해당하는 item을 지웠다.
최종적으로 queue의 최솟값, 최댓값을 알기위해서 또 map을사용했다.... 더효율적인 방법이 있을것이다.
다른사람 풀이1
function solution(arg) {
var list = [];
arg.forEach(t=>{
if(t[0] === 'I'){
list.push(+(t.split(" ")[1]));
}
else{
if(!list.length) return;
var val = (t[2] === '-' ? Math.min : Math.max)(...list);
var delIndex = list.findIndex(t=> t === val);
list.splice(delIndex, 1);
}
})
return list.length ? [Math.max(...list), Math.min(...list)] : [0, 0];
}
처음에 해당 풀이에서는 Number를 처리하지 않았다. 어디서 숫자로 바꾸어 주었는지 한참찾았는데, list.push(+ 부분을 발견했다. +를 붙이면 string이 number가 된다는것을 처음 알았다.
console.log(typeof "1")
console.log(typeof +"1")
>> string
>> number또한 number로 처음부터 queue(list)에 item을 push하면 두번이나 number로 처리를 해줄 필요도 없고, indexOf를 할때, string처리를 해줄 필요도 없었다.
또한 굳이 split을 사용하지않고 string 조건문을 만들수 있는 방법은 두가지이다. 다른 풀이를 보면 substring을 사용했다.(밑의 코드 참조)
하지만 string[index]를 사용하면 아주 간단하게 조건문 처리가 가능했다. string[index]는 해당 문자열의 index의 string을 반환한다.
다른사람 풀이2
const solution = (operations) => {
let answer = [];
for (let i = 0; i < operations.length; i++) {
const num = Number(operations[i].substring(2));
switch (operations[i].substring(0, 1)) {
case "I":
answer.push(num);
answer.sort((a, b) => {
return a - b;
});
break;
case "D":
if (num === 1) {
answer.pop();
} else {
answer.shift();
}
break;
}
}
if (answer.length === 0) {
return [0, 0];
}
return [answer[answer.length - 1], answer[0]];이중 우선순위큐의 개념을 적용한 풀이이다. sort를 이용해, queue(answer)를 정렬하고, pop과 shift를 이용해 itme을 제거한다. 또한 정렬이 되었기 때문에, return할때도 수월하다. 해당 풀이는 max, min을 사용하지 않는 다른 언어에서 꼭 필요한 아이디어일 것이다.
