Array(배열) - (선형)자료구조

 

Array (배열)은 같은 타입의 데이터를 여러개 나열한 선형 자료구조이다.

연속적인 메모리 공간에 순차적으로 데이터를 저장한다. 

✏️ Array의 시간 복잡도

1. 인덱스를 알고 있는 경우 요소에 접근하는 시간 복잡도 : O(1)
   ㄴ 배열은 인덱스를 이용하여 원하는 위치에 빠르게 접근 가능하다.
2. 삽입 삭제시의 시간 복잡도 : O(n) 
   ㄴ 삽입, 삭제시 해당 위치 이후의 모든 요소들을 이동시켜야하므로 성능이 좋진 않다. 

 

✏️ Array의 장점

1. 구현이 쉽다.
2. 인덱스를 통해 접근하므로 접근(검색)이 빠르다.
3. 연속된 메모리 공간에 저장하므로 메모리 공간을 효율적으로 관리할 수 있다.
4. 또한 순서대로 저장되므로 인접한 요소들에 대한 캐시 지역성이 좋아 성능 향상에 도움을 줄 수 있다. 
5. 참조를 위한 추가 메모리가 필요하지 않다.
6.  다차원으로 구현가능하다. (행렬과 같은 것을 표현할때 유용하다)

 

✏️ Array의 단점

1. 배열의 크기는 선언시 고정되므로 새로운 크기의 배열을  원할때는 다시 선언 후 옮겨야 한다.
2. 또한 같은 이유로 사용하지 않는 공간도 배열 선언시 할당되므로 메모리 공간 낭비가 생길 수 있다. 
3. 삽입, 삭제시 모든 요소들을 한 칸씩 옮겨야하므로 효율적이지 않다. (시간복잡도 O(n))

 

✏️ 번외) Array 선언시 한 칸에 할당되는 자료형의 크기 (대표적인 것만, 이외에도 많은 자료형이 있음)

• int : 4byte
• boolean : 1byte
• char : 1byte
• float : 4byte
• double : 8byte

 

✏️ Array 관련 문제들 

• 백준 10818번 : 최소, 최대  (순서대로 배열을 이용한 버전, Array.sort()를 이용한 버전)

package baekjoon.dataStructure.array;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Num10818 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int min = 1000000;
        int max = -1000000;
        for(int i=0; i<n; i++){
            if(arr[i] < min){
                min = arr[i];
            }
            if(arr[i] > max){
                max = arr[i];
            }
        }
        System.out.println(min + " " + max);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Num10818 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        System.out.println(arr[0] + " " + arr[n-1]);
    }
}

• 프로그래머스 : 나누어 떨어지는 숫자 배열

import java.util.Arrays;
class Solution {
    public int[] solution(int[] arr, int divisor) {
        int count = 0;
        for(int i=0; i<arr.length; i++){
            if(arr[i] % divisor != 0){
                arr[i] = -1;
            }else{
                count++;
            }
        }
        if(count == 0){
            int[] result = {-1};
            return result;
        }
        int[] answer = new int[count];
        Arrays.sort(arr);
        
        for(int i=0; i<count; i++){
            answer[i] = arr[arr.length-count+i];
        }
        
        return answer;
    }
}