기억하고싶은것들

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

정수 배열 nums와 정수 target이 주어진다.

배열의 두 수를 더해서 target이 되는 숫자를 반환하라.

주어진 배열에 정답이 되는 쌍은 정확히 하나이고, 같은 숫자들을 중복해서 사용할 수 없다.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

배열에 관련된 여러 문제를 풀면서 느꼈는데, 배열 문제를 푸는 시간 복잡도로는 크게 분류가 나누어진다.

O(n), O(nlogn), O(n^2)

각각의 방식들에 맞는 솔루션이 어떤 것이 있는지 고민하며, 가장 최적화된 방법으로 문제를 풀어나가 보자.

우선 가장 단순하게 배열을 2중으로 순회하며 값을 비교할 수 있다.

O(n^2)

    public int[] twoSum(int[] nums, int target) {

        for (int i = 0; i < nums.length - 1; i++) {
            int num1 = nums[i];
            for (int j = i + 1; j < nums.length; j++) {

                if (target - num1 == nums[j]) {
                    return new int[] { i, j };
                }
            }
        }

        return null;
    }

또한, HashMap을 이용해서 배열은 한 번만 순회하는 방법도 존재한다. 

O(n)

    // time complexity - o(n)
    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> map = new HashMap<>();
        int t = 0;
        for (int i = 0; i < nums.length; i++) {
            t = target - nums[i];
            if (map.containsKey(t)) {
                return new int[] { i, map.get(t) };
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

n+1개 integer를 가지고 있는 nums 배열이 주어진다.

각각의 원소의 범위는 [1, n]이다.

오직 하나의 숫자만 반복이 되는데, 그 숫자를 반환하라.

주어진 배열을 수정하지 말고, 추가적인 공간도 상수 개만 사용해서 문제를 풀어라.

해당 문제를 풀기 위해서는 Set, Map과 같은 추가적인 공간을 사용할 수도 있고,

Sorting을 통해서 인접한 원소들을 비교할 수도 있다. 

다만, 문제의 조건이 추가적인 공간이 상수 개이고, 정렬도 없다는 조건이므로 이러한 방식 이외의 것이 필요하다.

이 문제에서 중요하게 볼 부분은 배열에 주어진 값이 배열 인덱스 내의 값이라는 것이다.

즉, 배열의 값을 통해서 다른 배열로 포인팅이 가능해지고 해당 과정을 반복하며 2번 방문한 곳을 찾을 수 있다.

두 번 반복했는지 확인하기 위해서는 추가적인 공간을 사용하지 않고 주어진 배열을 활용할 수 있다.

방문한 배열의 값에 마이너스 표시 , 방문했을 때 배열의 값이 음수이면 중복 방문

    public int findDuplicate(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            int tmp = Math.abs(nums[i]);

            if (nums[tmp] < 0) {
                return tmp;
            } else {
                nums[tmp] = -nums[tmp];
            }
        }

        return -1;
    }

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

빨간색, 하얀색, 파란색으로 이루어진 n개의 요소를 가진 nums 배열이 주어진다.

새로운 배열을 선언하지 않고 제자리에서, 동일한 색이 서로 붙어 있도록 정렬을 하라.

순서는 빨간색 - 하얀색 - 파란색이다.

int값 0, 1, 2는 빨간색 - 하얀색 - 파란색을 나타낸다.

배열 기능이 존재하는 라이브러리를 사용하지 않고 문제를 풀어라. 

3개의 숫자로 이루어진 배열을 정렬해야 하는데, 추가적인 공간을 사용하지 않아야 한다.

배열의 맨 앞에 0과 swap할 포인터

배열의 맨 뒤에 2와 swap할 포인터를 둔다.

그리고 배열의 처음부터 끝까지 탐색할 포인터를 두어 해당 포인터의 값이 0이면 앞에 포인터와 swap

포인터의 값이 2이면 뒤에 포인터와 swap 하는 방식으로 문제를 해결할 수 있다.

다만, swap시 앞에 포인터에 해당하는 값은 탐색 포인터가 탐색한 값이므로 한번 더 체크할 필요가 없지만

뒤의 포인터와 swap한 값은 검증이 되지 않은 값이므로 체크해야 한다.

    public void sortColors(int[] nums) {
        int i = 0;
        int j = nums.length - 1;

        int p = 0;

        while (j >= p) {
            if (nums[p] == 0) {
                swap(i, p, nums);
                i++;
                p++;
            } else if (nums[p] == 2) {
                swap(j, p, nums);
                j--;
            } else {
                p++;
            }
        }
    }

    private void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

문제 출처 : 

https://leetcode.com/problems/sort-colors/

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

intervals[i] = [starti, endi]에 해당하는 interval 배열이 주어진다.

중복되는 모든 interval을 병합하라.

그리고 중복되는 interval이 없는 배열을 반환하라, 단 입력값으로 받은 모든 interval을 커버해야 한다.

배열의 각각의 범위가 중복되는 위치를 찾아야 한다.

처음에 주어진 내용만 본다면 어떻게 해야 하는지 감이 잡히지 않는다.

우선, 주어진 배열의 startIndex기준으로 정렬을 해보자.

어느 정도 정렬이 된다면, 앞에 배열과 뒤에 배열의 값들을 비교해주면 된다.

예를 들어 intervals[0][1] > intervals[1][0] 인 경우라면 중복되는 구역이 존재하는 것이다.

중복되는 구역이 존재한다면, 두 배열을 합치고 비교를 이어가면 된다.

시간 복잡도는 주어진 배열을 정렬하는 시간인 O(nlogn)이 소요된다.

    public int[][] merge(int[][] intervals) {

        // sorting - time complex - o(nlogn)
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int[][] rst = new int[intervals.length][2];
        rst[0] = intervals[0];
        int j = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (rst[j][1] >= intervals[i][0]) {
                // join
                rst[j][1] = Math.max(rst[j][1], intervals[i][1]);
            } else {
                rst[++j] = intervals[i];
            }
        }

        int[][] r = new int[j + 1][2];
        for (int i = 0; i < j + 1; i++) {
            r[i] = rst[i];
        }

        return r;
    }