📚 문제

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.

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

📝 문제 해결

좌/우 배열값의 합이 일치하는 pivot 인덱스를 찾는 문제로 전체 값의 합을 구한 다음 반복문을 돌면서 총합에서 좌측 배열의 값들을 빼다가 좌/우 배열값의 합이 같아지면 반복문을 종료하고 해당 인덱스를 반환해주면 된다.

요소 개수만큼 반복하므로 시간복잡도는 O(n)이 소요된다.

💻 코드

class Solution {
    public int pivotIndex(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int leftSum = 0;

        for(int i=0; i<nums.length; i++){
            int rightSum = total - nums[i] - leftSum;

            if(leftSum == rightSum){
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}

📚 문제

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

📝 문제 해결

이진탐색 문제로 이진탐색 알고리즘이란, 탐색 범위를 줄여 원하는 데이터를 찾는 시간 복잡도를 O(logN)으로 줄여주는 알고리즘으로

• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능
• 시간 복잡도 : O(logN) 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다

이진 탐색 동작방식

• 위치를 나타내는 변수 3개 (시작점, 끝점, 중간점)을 사용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교

1) 배열 / 시작점 / 끝점 / 찾고자하는 데이터 - 4개가 주어진다.
2) 시작점과 끝점의 중간점을 구한다.
3) 중간점이 가리키는 값이 찾고자하는 데이터면 끝
3-1) 중간점이 찾고자하는 데이터보다 크면 끝점을 중간점-1로,
3-2) 중간점이 찾고자하는 데이터보다 작다면 시작점을 중간점+1로 설정

이진 탐색 구현방법

• 재귀 함수

package search;

import java.util.Scanner;

public class search07 {
    public static int binarySearch(int[] arr, int target, int start, int end){
        if(start > end) return -1;
        int mid = (start + end)/2;
        if(arr[mid] == target) return mid;
        // 중간점의 값보다 작은 경우 왼쪽으로 끝점 이동
        else if(arr[mid] > target) return binarySearch(arr, target, start, mid-1);
        // 중간점의 값보다 큰 경우 오른쪽으로 시작점 이동
        else return binarySearch(arr, target, mid+1, end);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int target = sc.nextInt();

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        int result = binarySearch(arr, target, 0, n-1);
        if(result == -1) System.out.println("원소가 존재하지 않습니다.");
        else System.out.println(result+1);
    }
}

• 반복문

public static int binarySearch(int[] arr, int target, int start, int end) {
	while (start <= end) {
		int mid = (start + end) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 가급적 외우길 권함

더불어 범위가 큰 상황에서의 탐색을 가정하는 문제에 많이 나온다.

처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면,
이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려보자!

💻 코드

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;

        while(start <= end){
            mid = (start + end) / 2;
            if(target == nums[mid]) return mid;
            else if(nums[mid] < target) start = mid + 1;
            else if(target < nums[mid]) end = mid - 1;
        }

        return -1;
    }
}

📚 문제

Given an array nums. We define a running sum of an array as runningSum[i] = sum(num[0]...nums[i]).

Return the running sum of nums.

Example 1 :

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

💻 코드

class Solution {
    public int[] runningSum(int[] nums) {
        int[] sum = new int[nums.length];

        for(int i=0; i<nums.length; i++){
            for(int j=0; j<=i; j++) sum[i] += nums[j];
        }
        return sum;
    }
}

💡 다른 사람 코드

class Solution {
    public int[] runningSum(int[] nums) {
        for(int i=1;i<nums.length;i++)  nums[i]+=nums[i-1];
        return nums;
    }
}