기억하고싶은것들

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

integer 배열 nums가 주어지고, "pivot" 인덱스를 해당 배열에서 찾아라.

"pivot" 인덱스는 해당 인덱스를 기준으로 오른쪽 배열의 값들의 합과 왼쪽 배열의 값들의 합이 같은 경우를 말한다.

만약, 배열의 첫 번째 인덱스가 pivot이라면 왼쪽 배열의 합은 0이다, 왜냐하면 왼쪽에는 아무 배열도 없기 때문이다.

오른쪽도 마찬가지다.

가장 왼쪽에 위치하는 pivot 인덱스를 반환하라. 만약 존재하지 않는다면 -1을 반환하라.

우선 주어진 배열의 모든 값들을 더해서 totalSum으로 가지고 있고

하나의 포인터를 0번째 인덱스 기준으로 잡아 , 해당 포인터를 오른쪽으로 이동하며 totalSum에서 빼며 

움직인 요소들의 합과 값을 비교하는 식으로 문제를 해결해보자 ( Sliding ) 

    public int pivotIndex(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        int leftSum = 0;
        int pivot = 0;

        for (int i = 0; i < nums.length; i++) {

            pivot = i;
            totalSum -= nums[i];

            if (totalSum == leftSum) {
                return pivot;
            }
            leftSum += nums[i];
        }

        return -1;
    }

하나의 포인터를 기준으로 sliding 방식으로 문제 해결 

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index.

If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

"peak"는 양 옆의 숫자들보다 큰 경우를 말한다.

integer 배열 nums가 주어진다, 해당 배열에서 peak을 찾고 그 인덱스를 반환하라.

만약 배열에 여러게의 peak이 존재한다면, 어떠한 인덱스를 반환해도 된다.

배열 밖의 범위의 요소는 가장 작은 수로 인지하라 ( 즉, 맨 처음, 맨 뒤 인덱스의 값은 바로 옆 하나의 이웃보다 크면 peak이 된다)

반드시 시간 복잡도가 O(log n) 인 알고리즘을 작성하라.

배열의 search 알고리즘 문제의 시간 복잡도가 O(log n) 를 만족하기 위해서는 Binary Search를 사용해야 한다. 

결국 peak은 배열의 가장 큰 숫자를 찾으면 된다. 가장 크기 때문에 양옆의 숫자들보다 크기 때문이다.

배열의 가장 큰 숫자를 binary search로 찾는 문제로 생각하고 풀어보자.

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (right > left) { // binary search 
            int pivot = (left + right) / 2;
            if (nums[pivot] < nums[pivot + 1]) {
                left = pivot + 1;
            } else {
                right = pivot;
            }
        }
        return right;
    }

문제출처 : 

https://leetcode.com/problems/find-peak-element/

Given an integer array nums,

move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

integer 배열 nums가 주어진다. 

0을 배열의 맨뒤로 옮겨라, 단 0이 아닌 배열의 숫자 순서는 유지해야 한다.

주의 : 주어진 배열을 그대로 사용해야 한다. 다른 배열을 선언해서는 안된다.

두 개의 포인터를 이용하여서 배열의 맨 앞을 가리키도록 하여

하나는 값이 0인 배열의 인덱스를 가리키고

다른 하나는 0이 아닌 배열의 인덱스를 찾아 서로 위치를 바꾸어주도록 문제를 풀어보자 

    public void moveZeroes(int[] nums) {
        int idx = 0; // 0을 가르키는 포인터

        for (int i = 0; i < nums.length; i++) { // 0이 아닌 값을 찾는 포인터 
            if (nums[i] != 0) {
                swap(nums, i, idx);
                idx++;
            }
        }
    }

만약 배열의 첫 인덱스가 0이 아닌 경우에는 아래 for문에서 0을 가리키는 idx의 값이 ++ 되므로 0을 찾을 때까지 

idx, i가 같이 ++된다. 

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

문제출처 : 

https://leetcode.com/problems/move-zeroes/

Quick Sort는 배열을 기반으로 동작하기 때문에 배열에 대한 기본적인 설명을 한다.

Array (배열)

Random Access 가능 

Backtracking, Dynamic Programming과 같은 문제와 조합하여 많이 나옴

2차원, n차원 배열과 조합되는 문제 - graph

배열과 단골 조합 문제 - Sorting

Stable Sort - Merge Sort ( 정렬 후 조건이 같은 케이스는 순서가 변하지 않는다)

Unstable Sort - Quick Sort ( 정렬 후, 조건이 같은 케이스라도 순서가 변할 수 있다)

배열과 단골 조합문제 - Search 

정렬이 되어있지 않은 경우 O(n)

정렬이 되어있는 경우 - O(logn) (binary search) 

Quick Sort 

핵심 키워드 pivot, partitioning

하나의 리스트를 pivot을 기준으로 두 개의 부분 리스트로 나눈다.

부분 리스트 중에 하나는 pivot보다 작은 값들이 모여있는 리스트

다른 하나는 pivot보다 큰 값들이 모여있는 리스트로 구성된다.

각각의 부분 리스트에 대해서 다시 재귀적으로 위의 동작을 반복한다.

(분할 정복 - Divide and Conquer)

    private void quicksort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);

            quicksort(arr, left, pivot - 1);
            quicksort(arr, pivot + 1, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int low = left;
        int hight = right;

        int pivot = arr[left];

        while (low < hight) {
            while (arr[hight] > pivot && hight > low) {
                hight--;
            }

            while (arr[low] <= pivot && hight > low) {
                low++;
            }

            swap(hight, low, arr);
        }

        swap(left, low, arr);
        return low;
    }

    private void swap(int hight, int low, int[] arr) {
        int temp = arr[hight];
        arr[hight] = arr[low];
        arr[low] = temp;
    }

worst case - O(n*n)

best case - O(nlogn)