[Java] 코딩 테스트 개념 정리: 배열(Array)

1. 배열이 뭔데?

1-1. 배열의 핵심 특징

배열은 연속된 메모리 공간에 동일한 타입의 데이터를 순차적으로 저장하는 자료구조입니다.

• 고정 크기: 생성 시 크기를 지정하며, 한 번 정해진 크기는 변경할 수 없습니다.
• 인덱스 접근: 0부터 시작하는 인덱스를 통해 데이터에 직접 접근하므로 속도가 매우 빠릅니다.
• 논리적 순서 = 물리적 순서: 메모리 상에 데이터가 붙어 있어 CPU 캐시 효율이 좋습니다.

1-2. 시간 복잡도

연산	시간 복잡도	이유
인덱스로 접근/수정 (arr[i])	O(1)	주소 계산으로 바로 접근
전체 순회 (for)	O(n)	모든 원소를 한 번씩 확인
값 탐색(선형 탐색)	O(n)	최악의 경우 끝까지 확인 필요
정렬 (Arrays.sort)	평균 O(n log n)	비교 기반 정렬
중간 삽입/삭제(shift 발생)	O(n)	요소들을 한 칸씩 밀거나 당김

코테에서 “삽입/삭제가 자주 발생”한다면 배열 말고 다른 구조(ArrayList, Deque, LinkedList 등)도 같이 고려하는 게 좋습니다.

---

2. Java에서 배열 다루기

2-1. 생성 및 초기화

import java.util.Arrays;

int[] arr1 = new int[5];          // 0으로 초기화
int[] arr2 = {1, 2, 3, 4, 5};     // 선언과 동시에 초기화

Arrays.fill(arr1, -1);            // 특정 값으로 채우기

2-2. 자주 쓰는 유틸 (java.util.Arrays)

• 정렬: Arrays.sort(arr);
• 복사: Arrays.copyOf(arr, newLength); (새로운 배열 객체 생성)
• 출력: Arrays.toString(arr);
• 리스트 변환: Arrays.asList(arr); (객체 배열일 때만 기대한 대로 동작)

2-3. 다차원 배열 (2차원)

2차원 배열에서는 arr[row][col] 순서(행 → 열)를 헷갈리지 않도록 주의해야 합니다.

int[][] matrix = new int[3][3]; // 3x3 격자

int rows = matrix.length;       // 행의 개수
int cols = matrix[0].length;    // 열의 개수

---

3. ArrayList 정리

크기가 동적으로 변경되는 배열이 필요할 때 ArrayList를 활용합니다.

3-1. ArrayList란?

ArrayList는 Java의 대표적인 리스트 구현체로, 내부적으로 배열을 사용해 데이터를 저장합니다.
원소가 늘어나면 더 큰 배열을 만들어 복사(리사이징)하며 크기를 자동으로 확장합니다.

리사이징(Resizing) 동작 원리

• 초기 용량(capacity)은 기본 10개입니다.
• 원소가 늘어나 용량이 가득 차면, 내부 배열을 약 1.5배 크기로 새로 만들고 기존 데이터를 복사합니다.
• 이 때문에 개별 추가는 평균 O(1)이지만, 리사이징 시점에는 O(n)이 걸립니다. (Amortized O(1))
• 원소 개수를 미리 알면 new ArrayList<>(expectedSize)로 초기화하여 리사이징을 줄일 수 있습니다.

3-2. 배열 vs ArrayList 비교

항목	배열(Array)	ArrayList
크기 변경	불가능	가능(자동 리사이징)
접근/수정	O(1)	O(1)
맨 뒤 추가	직접 구현 시 O(n) 복사 필요	평균 O(1), 리사이징 시 O(n)
중간 삽입/삭제	O(n)	O(n)
타입	primitive 가능(int[])	객체만 가능(Integer)
메모리	상대적으로 효율적	오토박싱/객체 오버헤드 가능

고정 길이/성능 중심이면 배열, 가변 길이/구현 편의성이 필요하면 ArrayList를 선택합니다.

3-3. 기본 패턴

import java.util.*;

List<Integer> list = new ArrayList<>();

// 추가
list.add(10);           // 맨 뒤에 추가
list.add(0, 5);         // 인덱스 0에 삽입

// 조회
int v = list.get(0);

// 수정
list.set(0, 99);

// 삭제
list.remove(1);         // 인덱스 1 삭제
list.remove(Integer.valueOf(10)); // 값 10 삭제

// 크기
int size = list.size();

// 비었는지 여부 확인
boolean empty = list.isEmpty();

// 포함 여부 확인
boolean contains = list.contains(10);

// 정렬
Collections.sort(list);                    // 오름차순
list.sort(Comparator.reverseOrder());      // 내림차순

3-4. 주의사항

1) remove() 오버로드

ArrayList<Integer>에서 remove(1)은 “값 1 제거”가 아니라 인덱스 1 제거로 동작합니다.
값으로 제거하려면 Integer.valueOf()를 사용해야 합니다.

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));

list.remove(1);                    // 인덱스 1 삭제 → 값 2가 삭제됨
list.remove(Integer.valueOf(1));   // 값 1 삭제

2) primitive 배열 ↔ ArrayList 변환

// int[] -> List<Integer>
int[] nums1 = {1, 2, 3};
List<Integer> list1 = Arrays.stream(nums1)
                            .boxed()
                            .collect(Collectors.toList());

// List<Integer> -> int[]
List<Integer> list2 = List.of(1, 2, 3);
int[] nums2 = list2.stream()
                   .mapToInt(Integer::intValue)
                   .toArray();

3) Arrays.asList()는 객체 배열에서만 기대한 대로 동작

// 정상 동작
Integer[] objArr = {1, 2, 3};
List<Integer> ok = Arrays.asList(objArr);

// 주의: 원소 1개짜리 리스트처럼 동작
int[] primArr = {1, 2, 3};
List<int[]> weird = Arrays.asList(primArr);

---

4. 스트림(Stream) 활용

Java 8부터 도입된 스트림은 배열과 컬렉션을 다룰 때 가독성을 높여줍니다. 특히 필터링이나 변환 작업에서 유용합니다.

int[] nums = {1, 2, 3, 4, 5};

// 1. 필터링 및 변환
int[] evenSquared = Arrays.stream(nums)
                          .filter(n -> n % 2 == 0)
                          .map(n -> n * n)
                          .toArray();

// 2. 집계 (max, sum 등)
int max = Arrays.stream(nums).max().orElse(0);

// 3. 인덱스 기반 스트림 (IntStream)
int weightedSum = IntStream.range(0, nums.length)
                           .map(i -> nums[i] * i)
                           .sum();

---

5. 대표 패턴 및 실전 예제

5-1. 빈도 세기 (Counting)

값의 범위가 작을 때 배열 인덱스를 키(Key)로 활용합니다. ($O(n)$)

int[] count = new int[26];
for (char c : "hello".toCharArray()) {
    count[c - 'a']++; // 알파벳별 개수 저장
}

5-2. 투 포인터 (Two Pointers)

정렬된 배열에서 양끝 포인터를 좁혀가며 조건을 찾습니다. ($O(n)$)

Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;

while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return true;
    if (sum < target) left++;
    else right--;
}
return false;

5-3. 누적합 (Prefix Sum)

반복적인 구간 합 쿼리를 $O(1)$에 해결합니다.

int[] nums = {2, 1, 5, 3, 4};
int n = nums.length;

// 전처리: prefix[i] = 0부터 i-1까지의 합
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

// 구간 [l, r] 합
int l = 1, r = 3; // 1 + 5 + 3 = 9
int sum = prefix[r + 1] - prefix[l];

5-4. 슬라이딩 윈도우 (Sliding Window)

고정된 크기 또는 가변 크기의 윈도우를 배열 위에서 이동시키며 조건을 만족하는 구간을 찾습니다. ($O(n)$)

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int minLen = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];

        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }

    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

5-5. 카데인 알고리즘 (Kadane's Algorithm)

연속된 부분 배열의 최대 합을 구하는 DP의 기초 알고리즘입니다. ($O(n)$)

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        // [DP 로직] 현재 원소부터 새로 시작할지, 기존 합에 더해서 이어갈지 결정
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        
        // 전체 구간 중 가장 컸던 합을 갱신
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

5-6. 그래프 인접 리스트 (ArrayList 활용)

정점별 연결 정보를 저장해야 하는 그래프 문제에 활용합니다.($O(E)$)

import java.util.*;

public List<List<Integer>> buildGraph(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    for (int[] e : edges) {
        int u = e[0], v = e[1];
        graph.get(u).add(v);
        graph.get(v).add(u); // 무방향
    }
    return graph;
}

5-7. 2차원 배열 상하좌우 탐색

BFS/DFS로 격자에서 연결 요소 탐색, 최단거리, 영역 개수 세기, flood fill 등에 사용합니다. ($O(R*C)$)

import java.util.*;

public class GridBfsCount {
    static final int[] dr = {-1, 1, 0, 0};
    static final int[] dc = {0, 0, -1, 1};

    public static int countIslands(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        boolean[][] visited = new boolean[R][C];

        int count = 0;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    bfs(grid, visited, r, c);
                    count++;
                }
            }
        }
        return count;
    }

    private static void bfs(int[][] grid, boolean[][] visited, int sr, int sc) {
        int R = grid.length, C = grid[0].length;

        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{sr, sc});
        visited[sr][sc] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

                if (grid[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.add(new int[]{nr, nc});
                }
            }
        }
    }
}

---

6. 자주 하는 실수

1. 배열은 arr.length / 리스트는 list.size()
2. 2차원 배열 복사: matrix.clone()은 얕은 복사 -> 행마다 clone() 필요
3. ArrayList.remove(int index): 값이 아니라 인덱스 삭제임
4. 빈 배열 예외: max(), min() 같은 연산은 빈 배열 처리를 하지 않으면 에러가 날 수 있음 (orElse, 조건문)

---

마무리

배열은 코딩 테스트에서 가장 자주 등장하는 기본 자료구조이기 때문에 꼭 알아둘 필요가 있습니다.
이번에 내용을 정리하면서 다시 공부해보았는데, 특히 자주 쓰는 패턴들을 정리하는 과정이 큰 도움이 되었습니다.

다음 포스팅에서는 Stack/Queue를 정리해보겠습니다.🙌