꿀잠

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/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;  
    }  
}