23.09.26
📚 오늘 공부한 것
오늘 배운 것
자바스크립트 힙
- 최대힙
class MaxHeap(){
constructor(){
this.heap = [null];
}
push(value){
this.heap.push(value);
let currentIndex = this.heap.length -1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] < value){
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop(); //루트 정점을 가장 마지막 정점으로 대체
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while (
this.heap[currentIndex] < this.heap[leftIndex] ||
this.heap[currentIndex] < this.heap[rightIndex]
){
if (this.heap[leftIndex] < this.heap[rightIndex]){
const temp = this.heap[currentIndex]
this.heap[currentIndex] = this.heap[rightIndex];
this.heap[rightIndex] = temp;
currentIndex = rightIndex;
} else{
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[leftIndex];
this.heap[leftIndex] = tmp;
currentIndex = leftIndex;
}
leftIndex = currentIndex * 2;
rightIndex = currentIndex * 2 +1;
}
return returnValue;
}
}
const heap = new MaxHeap();
heap.push(45);
// ...
heap.pop()- 최소힙
class MinHeap(){ //최소힙 : 부모키값 < 자식키값
constructor(){
this.heap = [null];
}
push(value){
this.heap.push(value);
let currentIndex = this.heap.length -1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] > value){
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop(); //루트 정점을 가장 마지막 정점으로 대체
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while (
this.heap[currentIndex] > this.heap[leftIndex] ||
this.heap[currentIndex] > this.heap[rightIndex]
){
if (this.heap[leftIndex] < this.heap[rightIndex]){
const temp = this.heap[currentIndex]
this.heap[currentIndex] = this.heap[leftIndex];
this.heap[leftIndex] = temp;
currentIndex = leftIndex;
} else{
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[rightIndex];
this.heap[rightIndex] = tmp;
currentIndex = rightIndex;
}
leftIndex = currentIndex * 2;
rightIndex = currentIndex * 2 +1;
}
return returnValue;
}
}
const heap = new minHeap();안정 정렬 vs 불안정정렬
요소들 중 중복된 값들에 대해 정렬 후에도 입력 순서와 동일하게 정렬되면 “안정”
강의에서의 성능이 안정적이다와 다름!
자바스크립트의 sort
기본 함수 sort()를 쓰면 아스키코드 문자 순서대로 정렬된다!!!
우리가 원하는 숫자 크기대로 정렬을 하고 싶다면
const array = [1,43,2,7,29,343];
array.sort((a,b) => a-b ); //오름차순!!
array.sort((a,b) => b-a) ; // 내림차순 !!!문자열 반복
str.repeat(count);어려웠던 점
프로그래머스 - 가장 큰 수 문제 풀이 중 리턴 코드의 차이로 틀렸다는 체점 결과가 나와서 의문점이 생겼다.
일단, 전체코드는
function solution(numbers) {
var answer = '';
let newnum = []
for (let i =0; i<numbers.length; i++){
newn = (numbers[i]+'').repeat(3)
newnum.push([newn,i])
}
for (const n of newnum.sort().reverse()){
answer+=numbers[n[1]]
}
return (parseInt(answer)===0) ? '0' : answer;
}여기서
return (parseInt(answer)===0) ? '0' : answer; // << 성공!
if (answer[0] === '0'){ // << 성공!
return parseInt(answer)+"";
}else{
return answer
}
return parseInt(answer)+""; // << 실패 !!!![0,0,0] 인경우 ‘000’이 아닌 ‘0’을 출력해야하기에 숫자변환 후 문자변환 과정을 해서 반환했다.
그런데 위의 마지막처럼 코딩을 하니까 실패했다 ..
처음 생각:
위 예시처럼 0인 경우가 문제인지 아닌지를 확인하기 위해 두번째 반환코드를 작성해보았다.
저 코드가 성공했기에 0 인경우의 문제가 아니었다..
문제는 !
매우 큰 수에 대한 문자열, 숫자 변환이었다!
입력값은
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
이렇기 때문에 위와 같이 숫자 길이가 길~어지는 경우가 많을 것이다!
이때 parseInt(answer)+""; 처럼 숫자로 변환해버리면 “1e+39”와 같은 형태로 바뀌어 버리게 된 것이다 !!!!!!!!
결론!
큰숫자의 문자 변환을 주의하자!
0으로 처리해줘야 하는 경우를 따로 빼서 처리하고 나머지인 경우는 숫자변환이 필요없다!!!!
오늘 회고
Keep
자바스크립트로 자료구조, 알고리즘까지 구현해볼 수 있었다. 파이썬보다는 미숙하지만 계속해서 자바스크립트에 익숙함을 키우고 있다.
Problem
위에 적은 실습문제 return문 차이에 대해 트러블 슈팅 할 때 원인을 찾는데 시간이 오래걸렸다. 문제에도 큰 숫자에 대한 문자열 변환에 대해 언급이 있었는데 이부분을 간과했던 것 같다. 역시나 언제나 문제를 잘 읽자.
Try
질문을 더 잘하자! 팀원들에게 질문 했는데, 답변에서 요점이 많이 흐려져서 답답함을 느꼈다. 전체 코드를 보여주고 설명할 수 없었다는 제약은 있었지만, 의문인 곳에 대해 정확히 물어보자!
