Algorithm - Greedy (Container With Most Water, Jump Game, Jump Game II )

다용도리모콘·2021년 7월 24일

CodingTest

목록 보기

30/34

Container With Most Water

문제

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.

그래프 상에서 가장 크게 그릴 수 있는 사각형의 넓이를 구하는 문제.

코드

    function maxArea(height: number[]): number {
      let result = 0;
      let leftPointer = 0;
      let rightPointer = height.length - 1;

      while (leftPointer < rightPointer) {
        result = Math.max(
          result,
          (rightPointer - leftPointer) *
            Math.min(height[leftPointer], height[rightPointer]),
        );
        height[leftPointer] < height[rightPointer]
          ? leftPointer++
          : rightPointer--;
      }

      return result;
    }

회고

처음에 간단하게 이중 for문 돌렸다가 타임아웃 에러가 발생했다.
좌변, 우변의 값 중 작은 값이 높이가 되기 때문에 높이를 올리려면 둘 중 값이 작은 쪽 변을 이동시키면서 최대값을 비교해나가야 한다.
높이가 아닌 너비가 긴 경우가 최대값이 될 수 있기 때문에 비교는 그래프의 양 끝에서 시작해야 한다.

Jump Game

문제

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

코드

    function canJump(nums: number[]): boolean {
      let best = nums[0];
      for (let i = 1; i < nums.length; i++) {
        if (best >= i) {
          best = Math.max(best, nums[i] + i);
        }
      }
      return best >= nums.length - 1;
    }

회고

이번에도 재귀로 케이스를 돌다가 타임아웃이 발생했다.
키는 현재 이동할 수 있는 범위 내의 위치들을 기준으로 계속 해서 최대 이동거리를 구해나가는 것이다. 이해하고 나니 그리디의 정석인데 처음엔 이해가 잘 되지 않았던 문제.

Jump Game II

문제

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.

코드

    function jump(nums: number[]): number {
      let count = 0;
      let currentIndex = 0;

      while (currentIndex < nums.length - 1) {
        count += 1;
        const maxJumpIndex = currentIndex + nums[currentIndex];
        if (maxJumpIndex >= nums.length - 1) break;
        let maxIndex = currentIndex + 1;
        let maxValue = nums[maxIndex];

        for (let i = currentIndex + 1; i <= maxJumpIndex; i++) {
          if (maxValue <= nums[i] + i) {
            maxValue = nums[i] + i;
            maxIndex = i;
          }
        }
        currentIndex = maxIndex;
      }
      return count;
    }

    function jump(nums: number[]): number {
      let best = nums[0];
      let now = 0;
      let count = 0;

      if (nums.length == 1) return 0;

      for (let i = 0; i < nums.length; i++) {
        best = Math.max(best, nums[i] + i);
        if (i == now) {
          count++;
          now = best;
        }
        if (now >= nums.length - 1) break;
      }
      return count;
    }