💡 배열 (Array)

메모리 상에 원소를 연속으로 배치한 자료구조

• O(1)에 k번째 원소를 확인/변경 가능

• 추가적으로 소모되는 메모리의 양이 거의 없음

• 높은 Cache hit rate (캐시 메모리 적중률) : 메모리에서 해당 데이터를 찾아 제공

• 메모리 상에 연속한 구간을 잡아야 하므로 공간 할당에 제약 존재

📒 정리

• 임의의 위치에 있는 원소 확인 & 변경 : O(1)
• 마지막 위치에 원소 추가 & 마지막 위치의 원소 제거 : O(1)
• 임의의 위치에 원소 추가 & 제거 : O(N)

: 임의의 위치에 원소를 추가하는 경우, 해당 위치 이후의 원소들을 뒤로 한 칸씩 옮겨야 하므로 O(N)의 시간 복잡도가 발생한다. 제거도 마찬가지로 제거된 원소 이후의 원소들을 앞으로 한 칸씩 옮겨야 한다.

만약, 원소들을 옮기지 않는다면 메모리 상에 원소들이 더이상 연속적으로 위치하지 않아 배열의 정의를 위반하게 된다.

📒 연습문제

[10808] 알파벳 갯수

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        int[] cnt = new int[26];
        for(int i=0;i<s.length();i++) { // O(n)
            char ch = s.charAt(i);
            cnt[ch-97]++; // O(1)
        }

        StringBuilder sb = new StringBuilder();
        for (int i : cnt) {
            sb.append(i + " ");
        }
        System.out.println(sb);
    }
}

[1475] 방 번호

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] cnt = new int[10];
        int n = Integer.parseInt(br.readLine());

        while(n > 0) { // O(n)
            cnt[n % 10]++; // O(1)
            n /= 10;
        }

        int answer = 0;
        for(int i=0;i<cnt.length;i++) {
            if(i == 6 || i == 9) continue;
            answer = Math.max(answer, cnt[i]);
        }

        answer = Math.max(answer, (int)Math.ceil((double)(cnt[6] + cnt[9])/2));
        System.out.println(answer);
    }
}

[3273] 두 수의 합

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] cnt = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) { // O(n)
            cnt[i] = Integer.parseInt(st.nextToken()); // O(1)
        }

        int x = Integer.parseInt(br.readLine());
        Arrays.sort(cnt);

        int answer = 0;
        int start = 0;
        int end = n - 1;

        while(start < end) { // O(n)
            int sum = cnt[start] + cnt[end]; // O(1) + O(1)
            if(sum == x) answer++;

            if(sum <= x) start++;
            else end--;
        }

        System.out.println(answer);
    }
}

🙇🏻‍♀️ 출처 : [바킹독의 실전 알고리즘] 0x03강 - 배열