그리디 & 우선순위 큐 & MaxHeap

MaxHeap

class maxHeap {
  constructor() {
    this.heap = [];
    this.heap.push(Number.MAX_SAFE_INTEGER);
  }
  insert(val) {
    this.heap.push(val);
    this.upheap(this.heap.length - 1);
  }
  // pos = push한 값의 인덱스 번호
  upheap(pos) {
    let tmp = this.heap[pos];
    while (tmp > this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = tmp;
  }

  get() {
    if (this.heap.length === 2) {
      return this.heap.pop();
    }
    let res = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return res;
  }

  downheap(pos, len) {
    let tmp = this.heap[pos];
    let child;
    while (pos < parseInt(len / 2)) {
      child = pos * 2;
      // 우측 자식이 더 크면 child값 재할당
      if (child < len && this.heap[child] < this.heap[child + 1]) child++;
      if (tmp >= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  show() {
    for (let i = 1; i <= this.size(); i++) {
      console.log(this.heap[i]);
    }
    return true;
  }
}

---

동전교환

1. 최소값을 비교하기위해 answer에 안전한 최소값 할당
2. 반복문을 돌며 m이 n으로 나누어진다면 answer에 둘중 최소값 할당
3. m이 0이 될때까지 반복하는 while반복문 생성
4. 만약 m에서 nums배열 마지막값을 뺐을때 0보다 크거나 같다면 m에 차이값 할당
5. cnt++
6. 그렇지 않다면 nums의 마지막값 pop
7. 카운팅된 cnt값과 answer값을 비교하여 최소값을 answer에 할당
8. answer 반환

function solution(nums, m) {
  let cnt = 0;
  let answer = Number.MAX_SAFE_INTEGER;
  for (let n of nums) {
    if (m % n === 0) answer = Math.min(answer, m / n);
  }
  while (m > 0) {
    if (m - nums[nums.length - 1] >= 0) {
      m = m - nums[nums.length - 1];
      cnt++;
    } else {
      nums.pop();
    }
  }
  return Math.min(answer, cnt);
}

침몰하는 타이타닉

1. 슬라이딩을 위한 lt생성
2. 오름차순으로 정렬하여 중앙값으로 이동하는 lt변수와 rt변수 생성
3. lt변수와 rt변수가 중앙에서 만나거나 지나칠때까지 반복하는 while반복문 생성
4. 만약 끝과 끝값의 합이 m보다 작거나 같으면 answer에 카운팅하고 앞으로 한칸씩 이동
5. 그렇지 않다면 더 큰값을 빼고 answer 카운팅
6. 반복문이 끝나고 answer 반환

function solution2(nums, m) {
  let answer = 0;
  let lt = 0,
    rt = nums.length - 1;
  nums.sort((a, b) => a - b);
  while (lt <= rt) {
    if (nums[lt] + nums[rt] <= m) {
      answer++;
      lt++;
      rt--;
    } else {
      answer++;
      rt--;
    }
  }
  return answer;
}

회의실 배정

1. 이중 조건을 이용하여 meeting배열을 정렬
2. 끝나는 시간이 같다면 시작하는 시간을 기준으로오름차순 정렬
3. 그렇지 않다면 끝나는 시간을 기준으로 오름차순 정렬
4. 끝나는 시간을 할당해줄 et변수 생성
5. meeting배열에서 반복문을 돌며 배열값의 시작시간이 et와 같거나크다면
6. answer++
7. et에 끝나는 시간 할당
8. answer 반환

function solution(meeting) {
  let answer = 0;
  meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  });
  let et = 0;
  for (let x of meeting) {
    if (x[0] >= et) {
      answer++;
      et = x[1];
    }
  }
  return answer;
}

마지막 남은 수

1. 위쪽에 선언해둔 maxHeap참조
2. maxHeap클래스 생성
3. 반복문을 돌며 maxHeap에 nums배열값 insert
4. maxHeap이 빌 때까지 a변수와 b변수에 get한 값(Max값)을 할당
5. 만약 a와 b가 같지 않다면 maxHeap에 a-b값을 insert
6. 반복문이 끝난 후 maxHeap이 비어있다면 0반환
7. 남아있다면 남아있는 수 반환

function solution(nums) {
  let maxH = new maxHeap();
  for (let x of nums) {
    maxH.insert(x);
  }
  maxH.get();
  maxH.show();
  while (maxH.size() > 1) {
    let a = maxH.get();
    let b = maxH.get();
    if (a !== b) {
      maxH.insert(a - b);
    }
  }
  maxH.show();
  if (maxH.size() === 0) return 0;
  return maxH.get();
}

최대 수입 스케쥴

우선순위큐를 쓰는 대표적 그리디

1. 새로운 maxHeap 생성
2. 수용가능 날짜를 내림차순으로 정렬
3. maxday변수에 최고수용가능 날짜 할당
4. 전역으로 i를 쓰기위해 전역선언
5. 반복문을 돌며 day에 maxday를 할당한 후 1이될때까지 반복
6. 전역으로 선언한 i를 nums배열의 길이만큼 반복
7. 만약 돌고있는 배열의 날짜값이 day보다 작으면 break
8. (최고수용 날짜가 변했기 때문에 다음 반복문 실행 구문)
9. maxHeap에 급여값 insert
10. 이중 반복문이 끝난 후 만약 maxHeap이 존재한다면 answer 에 maxHeap에서 get한값 누적
11. 날짜만큼 반복한 반복문이 끝나고 answer 반환

function solution2(nums) {
  let answer = 0;
  let maxH = new maxHeap();
  nums.sort((a, b) => b[1] - a[1]);
  let maxday = nums[0][1];
  let i = 0;
  for (let day = maxday; day >= 1; day--) {
    for (; i < nums.length; i++) {
      if (nums[i][1] < day) break;
      maxH.insert(nums[i][0]);
    }
    if (maxH.size() > 0) {
      answer += maxH.get();
    }
  }
  return answer;
}

QUIZ1: 문자열 정렬

1. 새로운 Map 객체 생성
2. 첫번째 정렬기준(아스키값으로 오름차순)으로 s문자열 정렬
3. 반복문을 돌며 Map객체에 문자를 카운팅한 값 할당
4. 두번째 정렬기준(Map객체에서 많이 사용된 문자기준 내림차순)으로 Map객체 정렬
5. answer에 카운팅값만큼 문자를 반복한 문자열을 할당
6. answer 반환

function solution(s) {
  let sH = new Map();
  let sorted1 = s.split("").sort((a, b) => a.charCodeAt() - b.charCodeAt());
  for (let i = 0; i < sorted1.length; i++) {
    sH.set(sorted1[i], sH.get(sorted1[i]) + 1 || 1);
  }
  let sorted2 = [...sH.entries()].sort((a, b) => b[1] - a[1]);
  let answer = sorted2.map((e) => e[0].repeat(e[1]));

  return answer.join("");
}

QUIZ2: 누적곱 경우의 수 체크

1. 누적곱을 할당한 mul변수 생성
2. 반복문을 돌며 누적곱값 할당
3. 누적곱이 m(target)보다 크다면
4. 작거나 같아질때 까지 lt인덱스값만큼 나누고 lt++
5. answer에 모든 경우의 수 (rt - lt + 1) 누적
6. answer 반환

function solution(nums, m) {
  let answer = 0;
  let mul = 1,
    lt = 0;

  for (let rt = 0; rt < nums.length; rt++) {
    mul *= nums[rt];
    while (mul > m) {
      mul /= nums[lt++];
    }
    answer += rt - lt + 1;
  }
  return answer;
}

QUIZ3: 괄호안의 문자 반복

1. stack과 tmp배열 생성
2. 반복문을 돌며 ")"를 만나기 전까지 모두 stack에 push
3. ")"를 만나면 stack의 최상단값이 "("이 될때까지 tmp에 stack.pop()값을 unshift
4. stack.pop() ("("를 빼주는 구문)
5. "("를 뺀 후 스택에 최상단에 숫자가 있다면 loop에 stack.pop()한 값을 할당하고
6. 둘째자리까지 보기 위해 한번더 체크해서 loop문자 앞에 추가
7. loop를 숫자화한값 만큼 stack에 tmp안의 문자를 반복해서 push
8. tmp 초기화
9. 반복문을 탈출한 뒤 stack.join('')반환

function solution(s) {
  let stack = [],
    tmp = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ")") {
      while (stack[stack.length - 1] !== "(") {
        tmp.unshift(stack.pop());
      }
      stack.pop();
      if (!isNaN(stack[stack.length - 1])) {
        let loop = stack.pop();
        if (!isNaN(stack[stack.length - 1])) {
          loop = stack.pop() + loop;
        }
        for (let j = 0; j < parseInt(loop); j++) {
          stack.push(tmp.join(""));
        }
        tmp = [];
      }
    } else {
      stack.push(s[i]);
    }
  }
  return stack.join("");
}