Find Missing Range

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

문제를 정확하게 이해하는 것이 중요하다! 문제에서 묻는 것은 없는 범위의 숫자들을 찾는 것이 아니라 그 범위를 찾는 것이다! 주어진 예시를 통해 경우의 수를 커버한다고 생각하고 풀기!

Example 1 : Input : nums = [0,1,3,50,75], lower = 0 and upper = 99 Output : ["2", "4->49", "51->74", "76->99"]

Example 2 : Input : nums = [2,3,5,50,75], lower = 0 and upper = 99 Output : [0->1, 4, 6->49, 51->74, 76->99]

알고리즘 1. 경우의 수에 따라 코드를 세분화한다. 2-1. lower < nums[i] : (lower+1, nums[i]-1) 2. nums[i] + 1 < nums[i+1} : (nums[i]+1,nums[i+1}-1) 3. nums[nums.length-1] < upper : (nums[nums.length-1]+1,upper)

알고리즘을 java로 구현

package java_basic;

import java.util.*;
public class FindMissingRange {

	public static void main(String[] args) {
		int[] nums = {2,3,5,50,75};
		int lower=0, upper=99;
		System.out.println(solve(nums, lower, upper));
//		[0->1, 4, 6->49, 51->74, 76->99]
	}

	public static List<String> solve(int[] nums, int lower, int upper) {
		//0. 그릇 생성
		List<String> result = new ArrayList<>();
		//1. 기저사례 제외 
		if(nums == null || nums.length == 0) {
			result.add(getRange(lower,upper));
			return result;
		}
		//2. case#1 
		if(lower < nums[0]) {
			result.add(getRange(lower, nums[0]-1));
		}
		// case#2
		for(int i=0; i< nums.length;i++) {
			if(nums[i] != nums[i+1] && nums[i]+1 < nums[i+1]) {
				result.add(getRange(nums[i]+1, nums[i+1]-1));
			}
		}
		// case#3
		if(nums[nums.length-1] < upper) {
			result.add(getRange(nums[nums.length-1]+1, upper));
		}
		return result;
	}

	public static String getRange(int lower, int upper) {
		return lower == upper ? String.valueOf(lower) : (lower+"->"+upper);
	}

}