꿀잠

https://leetcode.com/problems/partition-labels/

같은 문자들은 한 구간으로 묶어 해당 구간들의 크기를 리턴하는 문제이다. 아이디어가 떠올라 쉬운 편인 문제였다. 현재 구간의 가장 마지막 끝은 구간 내의 모든 문자들을 포함 해야 하므로, 가장 큰 lastIndex의 값을 체크하면서 갱신하면 구간을 찾을 수 있다.

자바의 경우 String 클래스의 lastIndexOf 메서드를 통해 마지막 인덱스를 쉽게 찾을 수 있으므로 해당 메서드를 활용해서 문제를 해결해 주었다.

import java.util.*;  
  
public class Solution {  
    public List<Integer> partitionLabels(String s) {  
        List<Integer> answer = new ArrayList<>();  
  
        for(int i = 0; i < s.length(); i++){  
            int lastIdx = s.lastIndexOf(s.charAt(i));  
            int now = i;  
            while(now++ < lastIdx){  
                lastIdx = Math.max(lastIdx, s.lastIndexOf(s.charAt(now)));  
            }  
  
            answer.add(lastIdx - i + 1);  
            i = now - 1;  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/gas-station/description/

각 지역으로 이동을 위해 가스를 사용하고 충전하는 경우에 전체 지역을 한 바퀴 가능한지 확인하는 문제이다.

전체를 이동 가능한 지역은 하나로 유니크하며, 불가능할 경우 판단하여 -1을 리턴해야한다. 기본적으로 전체 지역을 완주하기 위해선 전체 가스의 총량이 전체 이동 코스트보다 낮아야 한다.

그렇기 때문에 0번 지역에서 부터 마지막 지역까지 확인하며 가스가 부족해지지 않는 시작 지점을 찾고, 완주할 전체 가스량이 된다면 이동이 가능하다는 것을 알 수 있다. 이러한 그리디 알고리즘으로 해결한 코드이다.

public class Solution {  
    public int canCompleteCircuit(int[] gas, int[] cost) {  
        int sum = 0;  
        int start = 0;  
        int total = 0;  
        for(int i = 0; i < gas.length; i++){  
            sum += gas[i] - cost[i];  
            if(sum < 0){  
                total += sum;  
                start = i + 1;  
                sum = 0;  
            }  
        }  
  
        total += sum;  
  
        return total >= 0  ? start : -1;  
    }  
  
}

https://leetcode.com/problems/jump-game-ii/

다음 인덱스까지 배열의 현재 값만큼 점프할 수 있을 때 몇번의 스텝으로 최종위치에 도달할 수 있는지에 대한 문제이다. 현재 점프할 수 있는 위치에서 점프 가능한 곳의 최소 값을 dp 배열에 저장하여 해결하였다.

import java.util.*;  
  
public class Solution {  
    public int jump(int[] nums) {  
        int n = nums.length;  
        int[] dp = new int[n];  
        Arrays.fill(dp, Integer.MAX_VALUE);  
        dp[0] = 0;  
  
        for(int i = 0; i < n; i++){  
            int jump = nums[i];  
            int step = dp[i] + 1;  
            int jumpMax = Math.min(i + jump, n - 1);  
            for(int j = i; j <= jumpMax; j++){  
                dp[j] = Math.min(dp[j], step);  
            }  
        }  
  
        return dp[n - 1];  
    }  
}

하지만 이 문제는 그리디 카테고리에 있는 알고리즘 문제이기에 그리디 방식으로 푸는 방식이 궁금해졌다. 다른 솔루션을 찾아 보니 그리디 방식의 경우 핵심 아이디어는 점프한 곳에서 다음 점프 시 가장 먼 곳으로 점프할 수 있는 곳 인지이다. 가장 먼 곳으로 점프하는 경우는 그 이전 구간도 전부 점프할 수 있으므로 점프 가능성을 최선의 선택으로 고르는 그리디 알고리즘이었다. 확인한 솔루션은 아래와 같다.

class Solution {  
    public int jump(int[] nums) {  
        return stepsToJumpFrom(nums, 0);  
    }  
  
    private int stepsToJumpFrom(int[] nums, int start) {  
        if (start >= nums.length - 1) {  
            return 0;  
        }  
        if (start + nums[start] >= nums.length - 1) {  
            return 1;  
        }  
        int furthestReachableNext = -1;  
        int nextStart = start;  
        for (int i = start + 1; i <= start + nums[start]; i++) {  
            if (i + nums[i] > furthestReachableNext) {  
                furthestReachableNext = i + nums[i];  
                nextStart = i;  
                if (furthestReachableNext >= nums.length - 1) {  
                    break;  
                }  
            }  
        }  
        return stepsToJumpFrom(nums, nextStart) + 1;  
  
    }  
}

https://leetcode.com/problems/jump-game/

0번 인덱스부터 최종 인덱스까지 각 인덱스에서의 nums[i] 수치만큼 이동할 수 있을때 끝까지 도달할 수 있는지에 대한 문제이다.

최종 목표지에 도달하기 위해선 특정 인덱스에서의 점프력(값이) 마지막 인덱스보다 높아야 한다.

그리고 해당 인덱스 까지 도달하기 위해서는 그 이전에서 점프력이 넘어야한다.

이를 반복해서 최초 시작 지점에서 목표 지점까지 뛸 수 있다면 가능하다고 할 수 있다.

배열을 역으로 내려오면 확인하며 풀었다.

public class Solution {  
    public boolean canJump(int[] nums) {  
        int goal = nums.length - 1;  
  
        for(int i = nums.length - 1; i >= 0; i--){  
            int num = nums[i];  
            if(i + num >= goal){  
                goal = i;  
            }  
        }  
  
        return goal == 0;  
    }  
}