[Level 3] 정수 삼각형

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=javascript

프로그래머스

 

 

풀이

처음 이 문제를 DFS 방식으로 풀이를 진행해 봤지만 시간 초과에러가 발생했다.

 

삼각형의 높이 즉, 주어지는 2차원 배열의 길이는 1~500 이였고 이는 1개씩 증가하는 수의 개수로 인해 경우의 수가 많아진다.

 

시간 복잡도로 인해 발생한 시간 초과 에러를 해결하기 위해서는 DP과 메모이제이션 알고리즘을 사용하기로 했다.

triangle 2중 배열을 메모이제이션으로 풀이를 진행한다.

 

총 두 가지 방법으로 문제를 풀어봤다.탑 다운, 바텀 업 방식으로 풀이했다.

 

탑 다운 방식은 두 개의 부모 노드중 큰 노드의 수를 더하는 방식이며, 이 풀이에서는 좌/우 부모노드의 존재가 있냐 없냐를 따져야 한다. 코드에서 ?? 연산자를 이용해 부모 노드 중 없는 노드면 0을 할당해 계산했다.

 

바텀 업 방식은 끝에서 2번재 노드열 부터 시작했으며 자식 노드 중 큰 노드의 수만 더해서 계산을 이어갔다.

 

개인적으로 코드의 난이도만 따졌을 때는 바텀 업 방식이 더 쉬웠던것 같다.

 

2024-11-08 다시 풀어봄

똑같이 DFS로 접근했다가 시간초과 에러를 맛보고 DP를 이용해 탑다운 방식으로 풀었다.
중간에 중복 연산되고 가장자리 숫자 검증으로 인해 시간초과가 발생했지만, 잘 해결했다.

 

코드

// 탑다운 방식
const solution = (triangle) => {
  for (let i = 1; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      const left = triangle[i - 1][j - 1] ?? 0;
      const right = triangle[i - 1][j] ?? 0;
      if (left >= right) {
        triangle[i][j] += left;
      }
      else {
        triangle[i][j] += right;
      }
    }
  }
  return Math.max(...triangle[triangle.length - 1]);
};

// 바텀업 방식
const solution = (triangle) => {
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
    }
  }
  return triangle[0][0];
};

 

 

다시 풀어본 코드

const solution = (triangle) => {
  const n = triangle.length;
    
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      if (j === 0) {
        triangle[i][j] += triangle[i - 1][j];
      }
      else if (j === triangle[i].length - 1) {
        triangle[i][j] += triangle[i - 1][j - 1];
      }
      else triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
    }
  }
  return Math.max(...triangle[n - 1]);
}