코딩 테스트를 위한 Java (2-1) - 정적 배열

이 글에서는 코딩 테스트에서 가장 기본임과 동시에 가장 많이 사용되는 자료구조인 배열(Array) 에 대해 살펴봅니다.

배열은 거의 모든 자료구조와 알고리즘의 기반이 되며, 문제 해결 과정에서 가장 먼저 고려해야 할 선택지이기도 합니다.

특히 코딩 테스트에서는

정렬, 투 포인터 (Two Pointer), 슬라이딩 윈도우 (Sliding Window), 누적합 (Prefix Sum), 동적 계획법 (DP)

등의 알고리즘들이 대부분 배열을 기반으로 동작합니다.

이번 장에서는 다음 내용을 다룹니다.

• Java 배열의 종류
• 원시형 배열과 객체 배열
• 다차원 배열과 Jagged Array
• 배열의 시간 복잡도

---

Java의 다양한 배열

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

Java의 배열은 다음과 같이 크게 두 가지 범주로 나눌 수 있습니다.

• 정적 배열
  • Primitive Array
  • Object Array
• 동적 배열
  • ArrayList
  • LinkedList

이 글에서는 정적 배열에 대해 먼저 살펴봅니다. 동적 배열(List 계열)은 다음 글에서 다룹니다.

---

원시형 배열(Primitive Array)

Java의 정적 배열은 객체(Object) 이며, 동적으로 생성됩니다.

int[] arr = new int[5];

In the Java programming language, arrays are objects,  are dynamically created, and may be assigned to variables of type Object . All methods of class Object may be invoked on an array.

https://docs.oracle.com/javase/specs/jls/se7/html/jls-10.html

Chapter 10. Arrays

 

즉 배열은 다음과 같이 Object 타입으로도 참조할 수 있습니다.

int[] arr = new int[5];
Object ref = arr; // int[] → Object
arr[0] == ((int[]) ref)[0]; // true

 

빠른 접근과 수정

배열은 메모리 상에 연속적으로 저장되므로, 인덱스를 통한 접근과 수정은 $O(1)$의 시간 복잡도를 가집니다.

arr[0] = 123;
System.out.print(arr[0]); // O(1)

배열은 크기가 고정되어 있기 때문에, 실제 삽입(insert)이나 삭제(delete) 연산이 존재하지 않습니다.

하지만 배열을 기반으로 리스트를 구현할 경우 중간 위치에 요소를 추가하거나 제거하려면

뒤쪽 요소들을 이동시켜야 합니다.

따라서 이러한 연산의 시간 복잡도는 $O(N)$이 됩니다.

 

배열에서의 삽입 구현

배열에서 "삽입"을 구현하려면 다음과 같이 요소 이동을 직접 구현하면 됩니다.

// arr[pos]에 value를 삽입 전 [pos + 1 ~ size] 영역의 요소를 한 칸씩 밀기
for (int i = size; i > pos; --i) {
    arr[i] = arr[i - 1];
}
arr[pos] = value;

 

 

배열의 길이

배열의 길이는 length 필드를 통해 $O(1)$안에 알 수 있습니다.

The public final field length, which contains the number of components of the array. length may be positive or zero.

int n = arr.length; // O(1)

https://docs.oracle.com/javase/specs/jls/se21/html/jls-10.html#jls-10.7

Chapter 10. Arrays

 

---

객체 배열 (Object Array)

배열은 원시형뿐만 아니라 객체 타입도 저장할 수 있습니다.

Integer[] arr = new Integer[5];

객체 배열은 내부적으로 다음과 같은 구조를 가집니다.

즉 배열에는 객체가 아니라 객체의 참조(reference) 가 저장됩니다.

---

원시형 vs 객체 배열

Java 배열은 원시형 타입과 객체 타입을 모두 저장할 수 있습니다.

예를 들어 다음 두 배열은 겉보기에는 비슷하지만 내부 구조가 크게 다릅니다.

int[] a = {1,2,3};
Integer[] b = {1,2,3};

 

저장 방식	값 저장	참조 저장
메모리 사용	적음	큼
성능	빠름	느림
null	불가	가능
읽기/수정	O(1)	O(1)
삽입/삭제	O(N), 논리적 구현	O(N), 논리적 구현

객체형 배열은 원시형 배열에 비해 다음과 같은 단점이 있습니다.

• 불필요한 객체 생성: 값을 감싸는 wrapper 객체가 추가로 생성됩니다.
• 자동 오토박싱: wrapper객체 ↔ 값 간 박싱과 언박싱이 자동으로 수행됩니다.

따라서 코딩 테스트에서는 가능하면 원시형 배열 사용이 권장됩니다.

 

 

객체 배열이 필요한 경우

그럼에도 불구하고 객체 배열이 필요한 상황이 존재합니다.

대표적인 경우는 다음과 같습니다.

 

Comparator를 사용하는 정렬

Primitive 배열은 Comparator를 사용할 수 없습니다.

int[] arr = {3,1,2};
Arrays.sort(arr, (a,b) -> b - a); // 컴파일 에러

Integer[] arr = {3,1,2};
Arrays.sort(arr, (a,b) -> b - a); // 가능 
/*
Arrays.sort(T[] a, Comparator<? super T> c)
*/

Arrays.sort()는 원시형 배열 정렬에는 값 비교 기반 빠른 정렬(Dual-Pivot QuickSort)을 수행하기 때문입니다.

객체형 배열 정렬시에만 TimSort를 지원합니다.

 

원시형 타입을 지원하지 않는 Collections API

Java의 대부분의 컬렉션 API는 객체 타입만을 지원합니다.

따라서 컬렉션의 타입을 원시형 타입으로 선언할 수 없습니다.

List<int> list = new ArrayList<>();     // 불가능
List<Integer> list = new ArrayList<>(); // 가능
List<int[]> list = new ArrayList<>();   // 배열은 객체이므로 가능

---

비정형 배열 (Jagged Array)

Java의 다차원 배열은 각 행의 길이가 달라도 됩니다.

int[][] metrix = new int[2][];
metrix[0] = new int[2];
metrix[1] = new int[5];

/*
metrix = {
    { 0, 0 },
    { 0, 0, 0, 0, 0 }
}
*/

이는 C/C++의 정적 2차원 배열과는 다른 특징입니다.

A multidimensional array need not have arrays of the same length at each level.

https://docs.oracle.com/javase/specs/jls/se21/html/jls-15.html#jls-15.10.2