[프로그래머스][그리디] n+1 카드게임

     

목차

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258707

프로그래머스

 

 

문제 구현 시 아이디어

문제 그대로 따라가면 무조건 시간초과가 나는 문제이다. 처음에 백트래킹으로 개고생했다..

그래서 더 생각해보아야 한다. 핵심 아이디어는 다음과 같다.

 

 

매 라운드마다 뽑은 카드를 바로 사용할지 판단하는게 아니라
기억해두었다가 미래에 필요할 때 사용하고 coin도 그 때 지불하면 되는것이다

 

틀린 풀이

let answer = 1;

function slidingWindow(arr, tg) {
  arr.sort((a, b) => a - b);
  let left = 0;
  let right = arr.length - 1;
  const ans = [];

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum < tg) left++;
    else if (sum > tg) right--;
    else {
      ans.push([arr[left], arr[right]]);
      left++;
      right--;
    }
  }
  return ans;
}

function dfs(idx, myCards, cards, coin, score, round) {
  if (idx >= cards.length) {
    answer = Math.max(answer, round);
    return;
  }

  const a = cards[idx];
  const b = cards[idx + 1];
  const copyCards = [...myCards];

  for (let i = 0; i < 4; i++) {
    if ((i === 0 || i === 1) && coin >= 1) {
      const newCards = [...myCards, i === 0 ? a : b];
      const set = new Set(newCards);
      const ready = slidingWindow([...set], score);

      if (ready.length === 0) {
        answer = Math.max(answer, round);
        continue;
      }

      for (const [c1, c2] of ready) {
        set.delete(c1);
        set.delete(c2);
        dfs(idx + 2, [...set], cards, coin - 1, score, round + 1);
        set.add(c1);
        set.add(c2);
      }

    } else if (i === 2) {
      const set = new Set(myCards);
      const ready = slidingWindow([...set], score);

      if (ready.length === 0) {
        answer = Math.max(answer, round);
        continue;
      }

      for (const [c1, c2] of ready) {
        set.delete(c1);
        set.delete(c2);
        dfs(idx + 2, [...set], cards, coin, score, round + 1);
        set.add(c1);
        set.add(c2);
      }

    } else if (i === 3 && coin >= 2) {
      const newCards = [...myCards, a, b];
      const set = new Set(newCards);
      const ready = slidingWindow([...set], score);

      if (ready.length === 0) {
        answer = Math.max(answer, round);
        continue;
      }

      for (const [c1, c2] of ready) {
        set.delete(c1);
        set.delete(c2);
        dfs(idx + 2, [...set], cards, coin - 2, score, round + 1);
        set.add(c1);
        set.add(c2);
      }
    }
  }
}

function solution(coin, cards) {
  const n = Math.max(...cards);
  const choose = Math.floor(n / 3);
  const myCards = cards.slice(0, choose);

  dfs(choose, [...myCards], cards, coin, n + 1, 1);

  return answer;
}

 

 

정정한 그리디 풀이

function solution(coin, cards) {
  let answer = 1;
  const n = Math.max(...cards);
  const choose = Math.floor(n / 3);

  let hand = [];
  let keep = [];

  for (let i = 0; i < choose; i++) {
    hand.push(cards.shift());
  }

  while (cards.length) {
    let a = cards.shift();
    let b = cards.shift();
    let canSubmit = getPairHand(hand, n + 1);

    if (canSubmit) {
      hand = hand.filter((item) => !canSubmit.includes(item));
      keep.push(a, b);
      answer++;
      continue;
    }

    if (coin >= 1) {
      keep.push(a, b);
      let canSub = getPairToOne(hand, keep, n + 1);

      if (canSub) {
        keep = keep.filter((item) => item !== canSub[1]);
        hand = hand.filter((item) => item !== canSub[0]);
        coin--;
        answer++;
        continue;
      }

      if (coin >= 2) {
        let canSubKeep = getPairHand(keep, n + 1);
        if (canSubKeep) {
          keep = keep.filter((item) => !canSubKeep.includes(item));
          coin -= 2;
          answer++;
          continue;
        }
      }
    }

    break;
  }

  return answer;
}

function getPairHand(hand, tg) {
  for (let i = 0; i < hand.length; i++) {
    for (let j = 0; j < hand.length; j++) {
      if (i !== j && hand[i] + hand[j] === tg) {
        return [hand[i], hand[j]];
      }
    }
  }
  return null;
}

function getPairToOne(hand, keep, tg) {
  for (let h of hand) {
    for (let k of keep) {
      if (h + k === tg) {
        return [h, k];
      }
    }
  }
  return null;
}