[LeetCode] Array and String - 1. Introduction to Array

▷ LeetCode 자료구조 이론 공부하며 번역 + 요약 정리

Introduction to Array

• 배열은 데이터 구조에서 기본 블록 중에 하나이다.
• string은 문자 배열(char 배열)로 형성되었기 때문에, array와 string은 비슷하다고 할 수 있다.

(참고) https://devlog-wjdrbs96.tistory.com/135

배열은 순차적으로 요소의 집합 a collection of elements 을 저장하는 기본 데이터 구조이다. 그러나 배열의 각 요소는 배열의 인덱스로 인식되기 때문에 요소들에 무작위로 접근할 수 있다.

배열은 하나 또는 그 이상의 차원을 가질 수 있다. 선형 배열 (linear array ) 라고 불리는 1차원 배열을 보자.

위의 예시를 보면 배열 A에는 6개의 요소 (elements)가 있다. 즉 배열 A의 길이는 6이다.
우리는 배열에서 첫번째 요소를 나타내기 위해 A[0]을 사용할 수 있다.
즉 A[0]은 6이고, 마찬가지로 A[1] = 3, A[2] = 8 … 이 된다.

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {

        // 1. 초기화하기
        int[] a0 = new int[5];
        int[] a1 = {1, 2, 3};

        // 2. 길이 구하기
        System.out.println("The size of a1 is: " + a1.length);

        // 3. 요소 접근하기 
        System.out.println("The first element is: " + a1[0]);

        // 4. 모든 요소 반복하기
        System.out.print("[Version 1] The contents of a1 are:");
        for (int i = 0; i < a1.length; ++i) {
            System.out.print(" " + a1[i]);
        }
        System.out.println();
        System.out.print("[Version 2] The contents of a1 are:");
        for (int item: a1) {
            System.out.print(" " + item);
        }
        System.out.println();

        // 5. 요소 수정하기
        a1[0] = 4;

        // 6. 정렬하기
        Arrays.sort(a1);
    }
}

Introduction to Dynamic Array

이전 글에서 언급한대로, 배열은 고정된 용량을 가지고, 초기화할 때 배열의 크기를 구체화해줘야 한다. 때때로 이건 낭비스럽고 불편하다.

따라서, 대부분 프로그래밍 언어는 무작위로 접근할 수 있는 리스트 (random access list )데이터 구조이면서, 크기가 고정되어있지 않은(variable size) '동적 배열' (dynamic array)을 제공한다. 예를 들면 C++에서 vector 와 자바에서 ArrayList가 해당된다.

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        **// 1. 초기화하기
        **List<Integer> v0 = new ArrayList<>();**
        **List<Integer> v1;                           // v1 == null**

        **// 2. 배열을 ArrayList로 cast하기**
        Integer[] a = {0, 1, 2, 3, 4};
        **v1 = new ArrayList<>(Arrays.asList(a));**

        **// 3. 복사하기**
        List<Integer> v2 = v1;                      // another reference to v1
        List<Integer> v3 = new ArrayList<>(v1);     // make an actual copy of v1

        **// 3. 길이 구하기**
        System.out.println("The size of v1 is: " + **v1.size()**);

        **// 4. 요소 구하기**
        System.out.println("The first element in v1 is: " + **v1.get(0)**);

        **// 5. ArrayList 반복하기**
        System.out.print("[Version 1] The contents of v1 are:");
        for (int i = 0; i < v1.size(); ++i) {
            System.out.print(" " + v1.get(i));
        }
        System.out.println();
        System.out.print("[Version 2] The contents of v1 are:");
        for (int item : v1) {
            System.out.print(" " + item);
        }
        System.out.println();

        **// 6. element 수정하기**
        **v2.set(0, 5);**       // modify v2 will actually modify v1
        System.out.println("The first element in v1 is: " + v1.get(0));
        **v3.set(0, -1);**
        System.out.println("The first element in v1 is: " + v1.get(0));

        **// 7. 정렬**
        Collections.sort(v1);

        **// 8. ArrayList의 끝에 새로운 요소 추가하기
        v1.add(-1);
        v1.add(1, 6);**

        **// 9. 마지막 요소 지우기
        v1.remove(v1.size() - 1);**
    }
}

Find Pivot index

pivot index는 인덱스의 왼쪽에 있는 모든 수의 합과, 인덱스의 오른쪽에 있는 모든 수의 합이 정확히 일치하는 인덱스를 말한다.

만약 인덱스가 배열의 왼쪽 끝에 있다면, 그 왼쪽 합은 0이다. 왜냐하면 왼쪽으로 요소들이 없기 때문이다.

제일 왼쪽의 pivot index를 리턴하라. 만약 그런 인덱스가 없다면 -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

접근법 #1: Prefix Sum [Accepted]

Intuition and Algorithm
우리는 모든 인덱스의 왼쪽으로의 합과 오른쪽으로의 합을 빠르게 계산할 필요가 있다.

숫자들의 합으로 S를 알고 있고, 인덱스 i에 있다고 해보자. 만약 인덱스 i의 왼쪽으로의 합 leftsum을 알고 있다면, 오른쪽으로의 합은 S - nums[i] - leftsum 이 된다.

→ 전체 - 해당 인덱스의 값 - 왼쪽합

이와 같이, 우리는 constant time (상수 시간)에서 해당 인덱스가 pivot index인지 아닌지 체크하기 위해서 leftsum만 알면 된다. 후보 인덱스 i를 반복하면서, 우리는 leftsum의 정확한 값을 유지하면 될 것이다.

복잡도 분석

• 시간 복잡도: O(N)O(N) (where NN is the length of nums.)
• 공간 복잡도 : O(1)O(1) (the space used by leftsum and S.)

class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0, leftsum = 0;
        for (int x: nums) sum += x;
        for (int i = 0; i < nums.length; ++i) {
            if (leftsum == sum - leftsum - nums[i]) return i;
            leftsum += nums[i];
        }
        return -1;
    }
}

Largest Number At Least Twice of Others

https://leetcode.com/explore/learn/card/array-and-string/201/introduction-to-array/1147/
다른 수의 최소 두 배 이상 큰 수

Plus One

https://leetcode.com/explore/learn/card/array-and-string/201/introduction-to-array/1148/
각 자리 수를 배열의 요소로 담을 때,
+1한 수를 배열의 요소로 담았을 때의 결과 출력