[코딩테스트, LeetCode] 문제풀이 #35, #53, #217, #278

35. Search Insert Position

sorting된 int array와 target이 주어지면 target의 인덱스, 혹은 있어야 할 자리를 반환하는 문제이다.
while(start<end)를 하면 Wrong Answer가 뜨는데, 이 문제의 경우 target이 array에 속하지 않을 가능성도 있기 때문에 <=로 하여야 한다.
mid를 (start + end)/2 가 아닌 start + (end-start)/2로 해야 overflow 방지가 된다고 한다.
실행시간 0ms

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length -1;
        
        while(start <= end){
            int mid = start + (end-start)/2;
            if(nums[mid] == target) return mid;
            else if (nums[mid] < target) start = mid + 1;
            else end = mid -1;
        }
        return start;
    }
}

278. First Bad Version

n개의 버전이 있을 때 v번째부터 이상한 코드가 섞였다고 하면 v번째 이후는 다 이상한 코드라고 가정한다. 이상여부를 감지하는 bool isBadVersion(version)가 주어진다고 했을 때 가장 처음 bad version인 v를 찾는 문제이다.
실행시간 12ms

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        //binary search ?
        int start = 1;
        int end = n;
        while(start < end){
            int mid = start + (end-start)/2;
            if(isBadVersion(mid)){
                end = mid;
            }
            else start = mid + 1;
        }
        return start;
 }

    }

217. Contains Duplicate

int array에 중복된 숫자가 있는지 검사하는 문제이다. sort를 해준뒤 앞 뒤 숫자를 비교해 주면 된다.
실행시간 5ms

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        
        for(int i=0; i< nums.length-1; i++){
            if(nums[i] == nums[i+1]) return true;
        }
        return false;
    }
}

53. Maximum Subarray

int array에서 연속된 부분 array 중 sum이 가장 큰 값을 출력한다.
(예시)
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Dynamic Programming의 일종인 카데인 알고리즘을 활용하면 되는데,다이나믹 프로그래밍의 핵심은 큰 문제를 작은 문제로 쪼개어 해결하고, 한번 풀었던 문제는 어딘가에 저장해두었다가 반복하여 풀지 않는 것이다.
실행시간 1ms

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int currentSum = sum;
        for (int i=1; i< nums.length; i++){
               currentSum = Math.max(nums[i], currentSum + nums[i]);
               sum = Math.max(sum, currentSum);
            
        }
        return sum;
    }
}