1 Greedy 짐 나르기

문제

김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.

예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.

박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.
박스의 무게 제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로 짐을 나르지 못하는 경우는 없습니다.

짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

입출력 예시
let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

풀이

새로운 사실

arr.sort([compareFunction]) : mutable

• compareFunction을 생략하면 배열의 element들이 문자열로 취급되어 유니코드 값 순서대로 정렬된다
• 두개의 배열 element를 파라미터로 입력 받는다

compareFunction(a,b){}
//배열의 요소를 둘씩 a,b로 받는다

• 함수가 리턴하는 값이 0보다 작으면 a가 b보다 앞에 오도록
• 0보다 크면 b가 a보다 앞에 오도록 정렬
• 0을 리턴하면 순서 변경 X

arr.sort(function(a, b)  {
  return a - b; //오름차순( a<b ) 이 결과가 음수면 뒤집도록 
  return b - a; //내림차순( a>b)
});

-원본 배열인 arr가 정렬이 되고 리턴하는 값 또한 원본 배열인 arr을 가리킨다

2 Greedy

문제

문제
편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다.
현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

입력
인자: k
number 타입의 k
1 <= k <= 100,000,000
출력
number 타입의 거스름돈 K원을 만드는데 필요한 동전 개수의 최솟값을 반환해야 합니다.

입출력 예시
// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = test1(4000);
console.log(output1); // --> 8

// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = test1(4972);
console.log(output2); // --> 18

풀이

function partTimeJob(k) {
  // TODO: 여기에 코드를 작성하세요.
  let arr =[500,100, 50, 10, 5, 1]; 
  let count=0;

  function getTimes(k){ 
    for(let a of arr){ 
      count += parseInt(k/a); 
      k = k % a;
    }
    return count;
  }

return getTimes(k)

}

3 구현

문제

N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.

좌표 왼쪽 상단(0, 0)에 말을 놓는다.
말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
조작의 기회는 딱 한 번 주어진다.
조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.
예시: UDDLLRRDRR, RRRRR
한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
보드 밖을 나간 말은 OUT 처리가 된다.
칸 안의 숫자는 0 또는 1이다.
단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.
획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.

입력
인자 1: board
number 타입의 2차원 배열
2 <= board.length <= 1,000
예: [ [0, 0, 1], [1, 0, 1], [1, 1, 1] ]
인자 2: operation
string 타입의 대문자 영어가 쓰여진 문자열

1 <= operation.length <= board.length * 2

U, L, D, R 이외의 문자열은 없습니다.
출력
Number 타입을 반환해야 합니다.
board와 operation이 입력값의 예시 ([ [0, 0, 1], [1, 0, 1], [1, 1, 1] ], DDR)일 때, (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) 순서로 이동하게 되고, 각 0, 1, 1, 1을 얻어 3을 반환합니다.
주의사항
만약, 말이 보드 밖으로 나갔다면 즉시 OUT 을 반환합니다.
입출력 예시
const board1 = [
[0, 0, 0, 1],
[1, 1, 1, 0],
[1, 1, 0, 0],
[0, 0, 0, 0]
]
const output1 = boardGame(board1, 'RRDLLD');
console.log(output1); // 4

const board2 = [
[0, 0, 1],
[1, 1, 1],
[1, 0, 0]
]
const output2 = boardGame(board2, 'UUUDD');
console.log(output2); // 'OUT'

const board3 = [
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0]
]
const output3 = boardGame(board3, 'DDRRRUDUDUD');
console.log(output3); // 0

풀이

function boardGame(board, operation) {
  // TODO: 여기에 코드를 작성하세요.
  //보드 밖을 나간 말은 OUT 처리가 된다.
  // HA 
  //board[row][column]

  //operation 문자열을 반복문 돌면서 if 
  //R : column++; 
  //L : column--;
  //U : row--; 
  //D : row++;
  //해당 값을 result에 더하기 

  //if(문자열 &&board[row][column] !== undefined){} 모든 조건문에 대해 
  //else로 return 'OUT'

  let row=0; 
  let column=0; 
  let result=0;

  for(let o of operation){ 
    if(o === 'R'){
      column++;
    if(row>=0 && column >= 0 && row<= board.length && column<=board[0].length){
              result += board[row][column]
    }
    else{ return 'OUT'}
    }
    if(o === 'L'){
      column--;
    if(row>=0 && column >= 0 && row<= board.length && column<=board[0].length){
              result += board[row][column]
      }
    else{ return 'OUT'}

    }

    if(o === 'U'){
      row--;
    if(row>=0 && column >= 0 && row<= board.length && column<=board[0].length){
              result += board[row][column]
      }
    else{ return 'OUT'}
    }

    if(o === 'D'){
      row++;
    if(row>=0 && column >= 0 && row<= board.length && column<=board[0].length){
              result += board[row][column]
      }
          else{ return 'OUT'}

    }

  }

  return result;

};

4 DP

https://leetcode.com/problems/coin-change/discuss/133487/clean-javascript-solution