알고리즘 스터디 39주차 - [프로그래머스] 광물 캐기, 할인 행사, 대충 만든 자판

1. 할인 행사 (Level 2)

Problem Summary

• want 배열에 있는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우의 수 구하기

Solution

function solution(want, number, discount) {
// 1. 물건과 물건의 개수를 매핑하기 
  const wantMap = want.reduce((map, el, idx) => {
    map.set(el, number[idx]);
    return map;
  }, new Map());

  let count = 10; // 물건 10개가 모두 할인되는지 체크해 줄 변수 
  let answer = 0;

  discount.forEach((_, i) => {
// 10개를 체크해줘야 하므로 이런 식으로 범위 정함 
// 지금 시작하는 값으로부터 10개 이상일 때에만 체크함 
    if (discount.length - i >= 10) {
      for (let j = i; j <= i + 10; j++) {
        const cur = discount[j];
        if (!wantMap.has(cur)) break; // 없는 품목이 있으면 바로 break
        if (wantMap.get(cur) <= 0) break; // 개수가 0이면 수량 안맞으니 break
        wantMap.set(cur, wantMap.get(cur) - 1); // wantMap의 해당 개수 감소 
        count -= 1;
      }

// 10개를 다 체크한 후 count가 10인지 확인 및 다시 채워주는 작업 
      if (count === 0) answer++;
      count = 10;
      want.forEach((v, i) => {
        wantMap.set(v, number[i]);
      });
    }
  });

  return answer;
}

Time Complexity

• O(N^2)
• discount 최대 길이가 10만이므로 10만의 제곱은 100억
• 100억이라서 100% 시간초과 날 줄 알았는데 통과됨

Another solution

function solution(want, number, discount) {
  let count = 0;

  const isItemCountWrong = (discount10, index) => {
    const filteredItemCount = discount10.filter((item) => item === want[index]).length;
    const itemCount = number[index];
    return filteredItemCount !== itemCount;
  };

  for (let i = 0; i < discount.length - 9; i++) {
    const discount10 = discount.slice(i, i + 10);

    let flag = true;

    for (let j = 0; j < want.length; j++) {
      if (isItemCountWrong(discount10, j)) {
        flag = false;
        break;
      }
    }
    if (flag) count += 1;
  }

  return count;
}

• discount 배열을 slice하여 10개 뽑아냄
• want 배열을 순회하는데, 이때 slice에 filter 메서드를 적용하여 number에 명시된 숫자만큼 slice에 물건이 존제하는지 체크한다.
  • 만약 수량이 다르면 flag를 false로 변경하고, break를 한다.

 

2. 대충 만든 자판 (Level 1)

Problem Summary

• keymap 배열에 있는 키 배열에 따라 target을 완성해야 하는데, 이때 target을 만들기 위한 최소 키 누르는 횟수
• 목표 문자열을 작성할 수 없다면 -1 리턴
• 특정 target의 알파벳을 누르고 난 후의 위치가 유지되는 것은 아니다.

Solution

function solution(keymap, targets) {
  const map = new Map();

  keymap.forEach((v) => {
    for (let i = 0; i < v.length; i++) {
      const keyName = v[i];
      const count = i + 1;
			// 현재 count가 이미 저장된 카운트보다 적다면 적은 값으로 교체해준다.
      if (!map.has(keyName) || map.get(keyName) > count) {
        map.set(keyName, count);
      }
    }
  });

  return targets.reduce((acc, target) => {
    let totalCount = 0;
    for (const el of target) {
      if (!map.get(el)) {
        totalCount = -1;
        break;
      }
      totalCount += map.get(el);
    }
    acc.push(totalCount);
    return acc;
  }, []);
}

• 특정 알파벳을 입력하기 위한 최소 횟수가 명시된 Map을 생성한다.
  • {알파벳: 입력 횟수(인덱스의 최솟값 + 1)}
• target 배열을 순회하면서 totalCount를 누적해준다.
  • 만약 map에 없는 요소라면 totalCount를 -1로 변경 후 break하여 바로 값을 배열에 push한다.

Time Complexity

• O(N) : 선형 시간 복잡도
• O(K * L)
  • K: keymap 배열의 원소 수 (최대 100)
  • L: targets 배열의 원소 수 (최대 100)
• keymap.forEach + for loop
  • 시간 복잡도 keymap 배열 원소 수 * keymap 배열의 원소 길이
• targets.reduce + for loop
  • target 배열 원소 수 * target 배열의 원소 길이

 

3. 광물 캐기 (Level 2)

Problem Summary

• 3가지의 곡괭이가 있고, 3가지의 광물을 캘 수 있는데 각각 피로도가 다르다.

다이아, 철, 돌 순으로 피로도가 적게 소모된다.

• 5개의 광물을 캔 후에는 더 이상 사용 불가능.

Solution

1. 곡괭이의 수만큼만 5개씩 광물 쌍을 만들어준다.
2. 각 쌍을 돌면서 다이아로 캤을 때의 피로도/철로 캤을 때의 피로도/돌로 캤을 때의 피로도 합을 구함
   • 피로도는 다이아로 캤을 때 가장 적을 거고, 돌로 캤을 때 가장 클 것
   • 피로도의 합으로 정렬을 할 것이기 때문에 피로도의 총합도 구해 준다.
   • { sum: 0, dia: 0, iron: 0, stone: 0 }
3. 피로도의 합이 큰 것이 뒤로 오도록 stack을 정렬해준다.
4. stack을 탐색하며 pop 하면서 가능하면 다이아 곡괭이부터 소진한다.
5. 곡괭이를 소진하며 피로도를 answer에 누적한다.

function solution(picks, minerals) {
  let answer = 0;

  const picksLength = picks.reduce((a, b) => a + b, 0) * 5; // 총 캘 수 있는 광물의 수
  const maxMinerals = Math.min(picksLength, minerals.length);

  // 캘 수 있는 광물만 딱 오기 때문에 queue를 쓰지 않아도 될 것
  const stack = [];
  // 5개씩 각 광물 개수 분석
  for (let i = 0; i < maxMinerals; i += 5) {
    const obj = { sum: 0, dia: 0, iron: 0, stone: 0 };
    for (let j = i; j < Math.min(i + 5, maxMinerals); j++) {
      if (minerals[j] === 'diamond') {
        obj.dia += 1;
        obj.iron += 5;
        obj.stone += 25;
      }

      if (minerals[j] === 'iron') {
        obj.dia += 1;
        obj.iron += 1;
        obj.stone += 5;
      }

      if (minerals[j] === 'stone') {
        obj.dia += 1;
        obj.iron += 1;
        obj.stone += 1;
      }
    }
    obj.sum += obj.dia + obj.iron + obj.stone;
    stack.push(obj);
  }

  stack.sort((a, b) => a.sum - b.sum); // 피로도 큰 것이 뒤로 오도록 정렬

  const pickMap = { dia: picks[0], iron: picks[1], stone: picks[2] };

  while (stack.length) {
    const { dia, iron, stone } = stack.pop();
    if (pickMap.dia) {
      answer += dia;
      pickMap.dia -= 1;
      continue;
    }
    if (pickMap.iron) {
      answer += iron;
      pickMap.iron -= 1;
      continue;
    }
    if (pickMap.stone) {
      answer += stone;
      pickMap.stone -= 1;
    }
  }

  return answer;
}

Time Complexity

• O(n log n)
  • minerals 배열을 5개씩 끊어서 분석 : 분석해야 하는 광물 개수는 minerals 배열 길이(n)에 비례 → O(n)
  • stack 정렬하는 시간 복잡도: O(n log n)
  • stack에 요소를 push, pop하는 시간 복잡도: O(1 * n)