[연습문제] 20. 86 ~ 89 정렬

in 코딩테스트 on 연습문제




탐욕 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

정렬 부시기!


86. 거스름돈 문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라.
단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

function factorial(n) {
  let arr = [500, 100, 50, 10];
  let cnt = 0;

  for (let i = 0; i < arr.length; i++) {
    while (arr[i] <= n) {
      n -= arr[i];
      cnt++;
    }
  }
  return cnt;
}

console.log(factorial(1350));
// 6

탐욕 알고리즘은 뭐랄까… 답이 안나올 때 도전해 보기 좋은 것 같지만 함정에 빠지기 쉽다.
이 문제의 경우는 상관이 없었지만 만약 400원이 있었다면, 800원일 때 500원 1개, 100원 3 개인 4개보다, 400원 2개가 나을 것이다. (이럴 경우는 dp로 풀어야 한다.)
때문에 탐욕 알고르즘은 너무 막막하면 시도해보긴 좋으나 dp나 다른 알고리즘도 분명 고려해봐야한다!



87. K 번째 수

프로그래머스 

function solution(array, commands) {
    let result = []
    for (let i =0; i< commands.length; i++){
        let arr = array.slice(commands[i][0]-1,commands[i][1])
        arr.sort((x,y) => x-y)
        result.push(arr[commands[i][2]-1])
    }
    return result
}



89. H-Index

프로그래머스 

function solution(numbers) {
    var answer = numbers
        .map((n) => n+"")
        .sort((x, y) => (y+x) - (x+y))
        .join("")
    return answer.split(0).join("") ? answer : "0"
}



89. H-Index

프로그래머스 

function solution(citations) {
  var answer = 0;
  citations.sort((x, y) => y - x);
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] >= i + 1) answer = i + 1;
  }
  return answer;
}


이전에는 어렵게 느껴지던 정렬이 더이상 어렵지 않게 됐다!
더 많은 문제를 풀어보고 싶은데 프로그래머스에는 3문제 뿐이어서 다른 사이트도 찾아봐야겠다.
sort 함수의 콜백 함수를 조금 더 활용할 수 있도록 노력하자!