[프로그래머스] 코딩테스트 공부

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

 

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

• 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
• 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

---

제한사항

• 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
  • 0 ≤ alp,cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
• alp_req는 문제를 푸는데 필요한 알고력입니다.
  • 0 ≤ alp_req ≤ 150
• cop_req는 문제를 푸는데 필요한 코딩력입니다.
  • 0 ≤ cop_req ≤ 150
• alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
  • 0 ≤ alp_rwd ≤ 30
• cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
  • 0 ≤ cop_rwd ≤ 30
• cost는 문제를 푸는데 드는 시간입니다.
  • 1 ≤ cost ≤ 100

정확성 테스트 케이스 제한사항

• 0 ≤ alp,cop ≤ 20
• 1 ≤ problems의 길이 ≤ 6
  • 0 ≤ alp_req,cop_req ≤ 20
  • 0 ≤ alp_rwd,cop_rwd ≤ 5
  • 1 ≤ cost ≤ 10

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

 

---

 

 

문제요점

알고력, 코딩력 1을 높이기 위해 1의 시간이 필요하다

모든 문제를 풀 수 있는 최단시간을 리턴해라

 

dp 풀이

알고력, 코딩력이 누적으로 늘어나기 때문에 dp가 떠올랐다.

dp의 요점: 순회하며 기존값과 새로운 값의 비교하여 갱신

이차배열 dp 

 

 

• 모든 문제를 풀기위해 최대알고력, 최대코딩력을 구한다
• 이를 이용해 dp 이차배열을 만든다 (나는 row=알고력, col=코딩력으로 설정했다)
• dp를 순회하며 알고력, 코딩력을 1씩 늘려가며 최단시간을 갱신한다. 단 이 때 최대알고력, 최대코딩력을 넘지 않게 주의한다.
• 능력이 늘고 풀 수 있는 문제가 있으면 해당 문제를 풀고 시간을 갱신한다.
• 이런식으로 순회가 끝난 뒤 dp[ maxAlp][maxCop] 최단시간을 리턴한다.

 

// 알고력, 코딩력 1을 높이기 위해 1의 시간이 필요
// 누적 dp
function solution(alp, cop, problems) {
  let maxAlp = alp;
  let maxCop = cop;
  problems.forEach(([alp, cop]) => {
    maxAlp = Math.max(maxAlp, alp);
    maxCop = Math.max(maxCop, cop);
  });

  const dp = Array.from({ length: maxAlp + 1 }, () =>
    Array.from({ length: maxCop + 1 }, () => Infinity)
  );
  dp[alp][cop] = 0;

  for (let currAlp = alp; currAlp <= maxAlp; ++currAlp) {
    for (let currCop = cop; currCop <= maxCop; ++currCop) {
      // 알고력1을 높였을때 최대필요 알고력을 넘지 않으면 알고력1을 높인 시간을 갱신
      if (currAlp + 1 <= maxAlp) {
        dp[currAlp + 1][currCop] = Math.min(
          dp[currAlp + 1][currCop],
          dp[currAlp][currCop] + 1
        );
      }
      // 코딩력1을 높였을때 최대필요 코딩력을 넘지 않으면 코딩력1을 높인 시간을 갱신
      if (currCop + 1 <= maxCop) {
        dp[currAlp][currCop + 1] = Math.min(
          dp[currAlp][currCop + 1],
          dp[currAlp][currCop] + 1
        );
      }
      // 풀 수 있는 문제가 있음 풀고 시간 갱신
      problems.forEach(([alp_req, cop_req, alp_rwd, cop_rwd, cost]) => {
        // 풀 수 있는 문제다
        if (currAlp >= alp_req && currCop >= cop_req) {
          // 문제를 풀어 점수를 얻어서
          const next_alp = Math.min(currAlp + alp_rwd, maxAlp);
          const next_cop = Math.min(currCop + cop_rwd, maxCop);
          dp[next_alp][next_cop] = Math.min(
            dp[currAlp][currCop] + cost,
            dp[next_alp][next_cop]
          );
        }
      });
    }
  }
  return dp[maxAlp][maxCop];
}

 

 

 

 

---

다른 풀이

 

다익스트라 = 가중치 그래프 + 우선순위 큐

 

function solution(alp, cop, problems) {
  var answer = 0;
  // 최대 알고, 코딩력 구하기
  let max_alp = alp;
  let max_cop = cop;
  problems.forEach(([req_alp, req_cop]) => {
    max_alp = Math.max(max_alp, req_alp);
    max_cop = Math.max(max_cop, req_cop);
  });

  // 초기 알고, 코딩력이 필요한 최대 알고, 코딩력보다 크면 바로 모든 문제를 풀 수 있다. ////////////////////
  if (alp >= max_alp && cop >= max_cop) {
    return 0;
  }

  const mq = new MinQueue();
  const visited = Array.from({ length: 151 }, () =>
    Array.from({ length: 151 }, () => false)
  );

  problems.push([0, 0, 1, 0, 1]);
  problems.push([0, 0, 0, 1, 1]);
  mq.enqueue({ cost: 0, alp, cop });

  // while (mq.heap.length > 1) {
  while (mq.heap.length - 1 !== 0) {
    const { cost, alp, cop } = mq.dequeue();
    if (visited[alp][cop]) {
      continue;
    }
    visited[alp][cop] = true;

    // 모든 문제를 풀수 있음
    if (alp >= max_alp && cop >= max_cop) {
      return cost;
    }
    problems.forEach(([req_alp, req_cop, plus_alp, plus_cop, plus_cost]) => {
      if (alp >= req_alp && cop >= req_cop) {
        //         const newAlp = Math.min(alp + plus_alp, max_alp);
        //         const newCop = Math.min(cop + plus_cop, max_cop);
        const newAlp = alp + plus_alp < max_alp ? alp + plus_alp : max_alp;
        const newCop = cop + plus_cop < max_cop ? cop + plus_cop : max_cop; // math.max 지양
        mq.enqueue({
          cost: cost + plus_cost,
          alp: newAlp,
          cop: newCop,
        });
      }
    });
  }
  answer = 0; 
  return answer;
}

// 다익스트라 우선순위 큐
class MinQueue {
  constructor() {
    this.heap = [null];
  }

  enqueue(data) {
    const { cost, alp, cop } = data;
    let currIndex = this.heap.length;

    // 2개이상일때 재정렬
    while (currIndex > 1) {
      const parentIndex = Math.floor(currIndex / 2);

      // 부모보다 자식이 더 작으면 swap
      if (this.heap[parentIndex].cost > cost) {
        this.heap[currIndex] = this.heap[parentIndex];
        currIndex = parentIndex;
      } else {
        break;
      }
    }
    this.heap[currIndex] = { cost, alp, cop };
  }

  dequeue() {
    const min = this.heap[1];
    if (this.heap.length > 2) {
      this.heap[1] = this.heap.pop();
      let currIndex = 1;
      let leftChildIndex = currIndex * 2;
      let rightChildIndex = currIndex * 2 + 1;

      while (this.heap[leftChildIndex]) {
        let smallerIndex = leftChildIndex;
        if (
          this.heap[rightChildIndex] &&
          this.heap[leftChildIndex].cost > this.heap[rightChildIndex].cost
        ) {
          smallerIndex = rightChildIndex;
        }

        if (this.heap[currIndex].cost > this.heap[smallerIndex].cost) {
          [this.heap[currIndex], this.heap[smallerIndex]] = [
            this.heap[smallerIndex],
            this.heap[currIndex],
          ];
          currIndex = smallerIndex;
        } else {
          break;
        }
        leftChildIndex = currIndex * 2; 
        rightChildIndex = currIndex * 2 + 1;
      }
    } else if (this.heap.length === 2) {
      this.heap.pop();
    } else {
      return null;
    }
    return min;
  }
}

 

 

 

느낀점

우선순위 큐는 js에서는 구현을 해야하고 배열상 인덱스 초과의 문제, 시간초과 등 문제가 많아서 개인적으로 dp가 더 간단하지만 강력한 풀이인 것 같다.