Array and String - Introduction to Array

Array & Dynamic Array

1. What is the difference between array and dynamic array?
2. What is the corresponding built-in data structure of array and dynamic array in your frequently-used language?
3. How to perform basic operations (initialization, data access, modification, iteration, sort, etc) in an array?
4. How to perform basic operations (initialization, data access, modification, iteration, sort, addition, deletion, etc) in a dynamic array?

 Introduction to Dynamic Array

- an array has a fixed capacity and we need to specify the size of the array when we initialize it. 

- Therefore, most programming languages offer built-in dynamic array which is still a random access list data structure but with variable size.  -> Arraylist in JAVA

 

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. initialize
        List<Integer> v0 = new ArrayList<>();
        List<Integer> v1;                           // v1 == null
        // 2. cast an array to a vector
        Integer[] a = {0, 1, 2, 3, 4};
        v1 = new ArrayList<>(Arrays.asList(a));
        // 3. make a copy
        List<Integer> v2 = v1;                      // another reference to v1
        List<Integer> v3 = new ArrayList<>(v1);     // make an actual copy of v1
        // 3. get length
        System.out.println("The size of v1 is: " + v1.size());
        // 4. access element
        System.out.println("The first element in v1 is: " + v1.get(0));
        // 5. iterate the vector
        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. modify 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. sort
        Collections.sort(v1);
        // 8. add new element at the end of the vector
        v1.add(-1);
        v1.add(1, 6);
        // 9. delete the last element
        v1.remove(v1.size() - 1);
    }
}

Problem1. Find pivot index (2ms, 53.7MB)

*** leftmost : 가장 맨 왼쪽의

class Solution {
    public int pivotIndex(int[] nums) {
        int frontSum = 0;
        int endSum = 0;
        for(int num : nums){
            endSum+=num;
        }
        
        for(int i = 0; i<nums.length;i++){
            endSum -=nums[i];
            if(frontSum == endSum) {
                return i;
            }
            frontSum +=nums[i];
        }
        return -1;
    }
}

 

Problem2 . Largest Number At Least Twice of Others (  0ms, 40.3MB)

class Solution {
    public int dominantIndex(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        //1. 제일 큰 숫자 찾아서 다른 숫자랑 2배에 해당하는지 찾기 -> O(n)
        int max = Integer.MIN_VALUE;
        int index = -1;
        for(int i = 0; i<nums.length;i++){
            if(nums[i]>=max){
                max= nums[i];
                index = i;
            }
        }
        
        for(int i = 0;i<nums.length;i++){
            if(index == i){
                continue;
            }
            if(nums[i]*2 > max){
                return -1;
            }
        }
        
        return index;
    }
}

PriorityQueue를 만들어서 최대값 최소값으로 구하는 방법도 있음

결국, 가장 큰 수와 가장 큰 수를 제외한 수 중 가장 큰 수의 두 배를 비교하기만 하면 되기 때문에 아래와 같이

성립할 수 있음

class Solution {
    public int dominantIndex(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(i -> nums[i]));
        
        for(int i = 0; i < nums.length; i++) {
            queue.add(i);
            
            if (queue.size() > 2) {
                queue.poll();
            }
        }
        
        if (queue.size() == 1) return queue.poll();
        int min = queue.poll(); 
        int max = queue.poll();
        
        if (nums[max] >= nums[min] * 2) return max;
        return -1;
    }
}

Problem3. Plus one ( 9ms, 43.5MB)

- 효율성이 정말 좋지 않지만, BigInteger에 대해서 공부하게 되었다.

일단 length가 100까지 될 수 있기에 int, long 둘 다 불가능하다.

long은 메모리 크기는 8byte로 표현할 수 있는 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

그 범위를 넘어서게 되면 모두 0으로 출력이 된다.00000 숫자의 범위가 저 범위를 넘을 경우는 잘 없겠지만 프로그램 개발 특히 돈과 관련된 개발이나 알고리즘 문제를 풀 때 항상 최악의 상황을 고려해야 하므로 무한의 정수가 들어갈 수 있는 가능성이 있다면 BigInteger이라는 클래스를 활용하는 것이 좋다. BigInteger은 문자열 형태로 이루어져 있어 숫자의 범위가 무한하기에 어떠한 숫자이든지 담을 수 있다.

** import java.math.BigInteger

** 더하기는 ArrayList처럼 <BigInteger이름>.add(<BigInteger 이름> )

** BigInteger to String => <BigInteger 이름>.toString()

import java.math.BigInteger;

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        if(digits[len-1] != 9){
            digits[len-1] += 1;
            return digits;
        }
        //digits[len-1] == 9 일때만 주의하면 됨.
        //length가 100까지 갈 수 잇어서 string->long->BigInteger
        String num = "";
        for(int digit:digits){
            num += digit;
        }
        BigInteger larger = new BigInteger(num);
        BigInteger one = new BigInteger("1");
        larger = larger.add(one);
        num = larger.toString();
        int [] result = new int [num.length()];
        for (int i = 0; i < result.length; i++){
            result[i] = num.charAt(i) -'0';
        }
        return result;
    }
}

BigInteger 연산방법

2번째 생각한 방법(0ms, 42.6MB)

어쨋든, 끝이 9가 아니라면 그냥 맨 끝의 수를 1 증가시키면 된다.

그런 다음, 9일 때의 경우만 처리해주면 된다.

9인 경우, 다 0으로 바꿔주고 마지막 index에 +1

그리고 맨 처음이 0인 경우를 다시 배열 크기를 증가시켜 처리

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        if(digits[len-1] != 9){
            digits[len-1] += 1;
            return digits;
        }
        //digits[len-1] == 9 일때만 주의하면 됨.
        int next = len-1;
        while(next>=0 && digits[next] == 9) {
            digits[next] = 0;
            next-=1;
        }
        if(digits[0] == 0){
            int[] result = new int[len + 1];
            result[0] = 1;
            for (int i = 1; i < digits.length; i++) {
                result[i] = digits[i - 1];
                }
            return result;  
        }
        digits[next] +=1;
        return digits;
    }
}