본문 바로가기

Java

코딩테스트 합격자 되기 (CHAPTER 5 배열)

CHAPTER 5 배열

배열의 개념에 대해 이해하고 활용하는 방법을 알 수 있습니다. 
코딩 테스트 난이도별로 배열 관련 문제를 풀며 여러 함정을 확인하고 이를 해결하는 방법에 익숙해집니다. 

5-1 배열 개념

배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위체이 있는 데이터든 한 번에 접근할 수 있습니다.

배열 선언

배열을 선언하는 방법은 다음과 같습니다. 이름이 arr이고 길이가 6인 정수형 배열을 선언하는 방법을 알아보겠습니다.

일반적인 방법

int[] arr = {0, 0, 0, 0, 0, 0}; 1️⃣
int[] arr = new int[6]; 2️⃣

이렇게 선언한 배열은 컴퓨터에 이런 모습으로 저장됩니다.

배열은 인덱스가 0부터 시작합니다. 즉, 3번째 데이터에 접근하려면 arr[2]와 같이 접근하면 됩니다. 1️⃣과 2️⃣는 결과값이 동일합니다. 자세히 말하자면 자바에서는 배열을 생성하면, int형 배열은 기본값을 0으로 초기화하므로 1️⃣과 2️⃣는 실행 결과가 동일합니다. 배열은 코딩 테스트에서 가장 많이 사용하는 자료구조이므로 확실히 알아두고 넘어가야 합니다.

자바에서는 배열과 유사한 기능을 가진 ArrayList 자료구조가 있습니다. 배열과 ArrayList의 차이점은 배열은 처음 선언할 때 배열의 크기가 결정되고, ArrayList는 크기가 동적이라는 것입니다. 따라서 정확한 데이터의 개수를 알 수 있다면 코드가 더 간결하고 속도가 더 빠른 배열을 사용하면 되고, 저장해야 할 데이터의 개수를 정확히 알 수 없다면 ArrayList를 사용하시면 됩니다.

❗️엄밀히 말하자면 ArrayList도 초기에 크기가 결정되자만 동적으로 변하는 것처럼 구현되어 있습니다.

배열과 차원

배열은 2차원 배열, 3차원 배열과 같이 다차원 배열을 사용할 때도 많습니다. 하지만 컴퓨터 메모리의 구조는 1차원이므로 2치원, 3차원 배열도 실제로는 1차원 공간에 저장됩니다. 다시 말해 배열은 차원과 무관하게 메모리에 연속 할당됩니다.

1차원 배열

1차원 배열은 가장 간단한 배열 형태를 가집니다. "간단하다"라고 말한 이유는 1차원 배열의 모습이 메모리에 할당된 실제 배열의 모습과 같다는 겁니다. 다음 그림을 보면 쉽게 이해할 수 있습니다.

왼쪽 그림이 1차원 배열의 모습이고, 오른쪽 모습이 실제 메모리에 배열이 할당된 모습입니다. 배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당됩니다.

2차원 배열

2차원 배열은 1차원 배열을 확장한 겁니다. 2차원 배열은 자바에서 다음과 같이 선언할 수 있습니다.

// 2차원 배열 생성 
int[][] arr = {{1,2,3}, {4,5,6}};
// arr[1][2]에 저장된 값을 출력
System.out.print(arr[1][2]); //6
// arr[1][2]에 저장된 값을 7로 변경 
arr[1][2] = 7;
// 변경된 값을 출력 
System.out.print(arr[1][2]); //7

2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷합니다. 행과 열을 명시해 [] 연산자를 2개 연이어 사용한다는 점만 다릅니다.

int[][] arr = {{1,2,3},{4,5,6}}; // 2행 3열 2차원 배열 선언

이를 그림으로 나타내면 다음과 같습니다.

왼족은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고, 오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 겁니다. 사람이 이해하기에는 왼쪽의 형태로 이해하는 것이 편리하므로 2차원 배열을 왼쪽의 행과 열 공간처럼 표현하는 경우가 많지만 실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장합니다. 이런 배열의 특성을 잘 기억해두기 바랍니다.


5-2 ArrayList 사용법

자바에서 크기가 동적으로 변경되는 배열이 필요할 때는 ArrayList를 활용합니다. 여기서는 코딩 테스트에 자주 활용하는 ArrayList 사용 방법에 대해서 알아보겠습니다.

ArrayList에 데이터 추가

여기서는 ArrayList에 데이터를 삽입하는 방법을 알아보겠습니다.

add()메서드로 데이터 추가

맨 끝에 데이터를 추가하려면 add() 메서드를 사용하면 됩니다.

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가
list.add(1); // [1]
list.add(2); // [1,2]
list.add(3); // [1,2,3]

다른 컬렉션의 데이터로부터 초기화

ArrayList의 생성자의 매개변수로 컬렉션을 넘기면 매개변수로 넘긴 컬렉션에 담긴 데이터로 초기화할 수 있습니다.

ArrayList<Integer> list = new ArrayList<>();
//리스트의 맨 끝에 데이터 추가 
list.add(1); // [1]
list.add(2); // [1,2]
list.add(3); // [1,2,3]

ArrayList<Integer> list2 = new ArrayList<>(list);
System.out.print(list2); // [1,2,3]

get() 메서드로 인덱스를 통해 데이터에 접근

특정 인덱스에 있는 데이터에 접근하기 위해서는 get() 메스드를 사용하면 됩니다.

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가 
list.add(1); // [1]
list.add(2); // [1,2]
list.add(3); // [1,2,3]

System.out.println(list.get(1)); // 2

remove() 메서드로 데이터 삭제

remove() 메서드를 사용하면 특정 위치의 데이터를 삭제할 수 있습니다.

ArrayList<Integer> list = new ArrayList<>();
// 리스트의 맨 끝에 데이터 추가 
list.add(1); // [1]
list.add(2); // [1,2]
list.add(3); // [1,2,3]

list.remove(list.size() -1); // 끝에 있는 데이터 삭제 
System.out.println(list); // [1,2]

다만 remove() 메서드는 데이터를 삭제하는 위치에 따라 데이터를 복사하는 연산이 필요하므로 시간 복잡도가 O(N)까지 증가할 수 있기 때문에 주의해야 합니다.

합격조언 깨알 같은 배열, ArrayList 연관 메서드

이외에도 코딩 테스트에서 활용하면 유용한 깨알 같은 몇 가지 기능을 코드와 함께 소개하겠습니다.

  • 배열의 전체 데이터 개수를 가진 length 변수
  • 배열의 모든 데이터를 정렬하는 Arrays 클래스의 sort() 메서드
  • 배열의 모든 데이터를 String으로 반환하는 Arrays 클래스의 toString()메서드
  • ArrayList의 전체 데이터 개수를 반환하는 size()메서드
  • ArrayList에 저장된 데이터가 없는지 여부를 반환하는 isEmpty()메서드
  • ArrayList의 모든 데이터를 정렬하는 Collections 클래스의 sort()메서드

5-3 ArrayList의 효율성

배열 연산의 시간 복잡도

배열 데이터에 접근할 때의 시간 복잡도를 알아봅시다. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단번에 접근할 수 있스비다. 따라서 데이터에 접근하기 위한 시간 복잡도는 0(1)입니다. 배열에 데이터를 추가하는 경우는 어떨까요? 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라집니다.

맨 뒤에 삽입할 경우

다음과 같은 배열이 있을 때 2를 추가한다고 생각해봅시다. 맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않습니다. 따라서 시간 복잡도는 0(1)입니다.

맨 앞에 삽입할 경우

데이터를 맨 앞에 삽입한다면 어떻까요? 이 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 합니다. 즉, 미는 연산이 필요합니다. 데이터 개수를 N개로 일반화하면 시간 복잡도는 0(N)이 되겠네요.

중간에 삽입할 경우

중간에 삽입할 경우도 보겠습니다. 5 앞에 데이터를 삽입한다면5 이후의 데이터를 뒤로 한 칸씩 필어야 할 겁니다. 다시 말해 현재 삽입한 데이터 개수만큼 미는 연산을 해야 합니다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 0(N)이겠네요.

배열을 선택할 때 고려할 점

데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있습니다. 예를 들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도0(1)로 판단할 수 있습니다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있습니다. 다시 말해 배열은 임의 접근이라는 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이니만 메모리 낭비가 발샐할 수 있습니다. 따라서 코딩 테스트에 서는 다음 사항을 고려해 배열을 선택하야 합니다.

  1. 할당할 수 있는 메모리 크기를 확인해야 합니다.

  2. 중간에 데이터 삽입이 많은지 확인해야 합니다.

5-4 몸풀기 문제

문제 01 배열 정렬하기

제약조건

  • 정수 배열의 길이는 2이상 10의 5제곱 이하입니다.
  • 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.

입출력의 예

입력 출력
[1,-5,4,3] [-5,1,2,3,4]
[2,1,1,3,2,5,4] [1,1,2,2,2,3,4,5]
[6,1,7] [1,6,7]

문제 분석하고 풀기

문제만 놀고 보면 간단해 보이지만 제약 조건은 주의 깊게 봐야 합니다. 제약 조건을 보면 데이터 개수는 최대 10의5승 입니다. 즉, 제한 시간이 3초라면 0(N2)알고리즘은 사용할 수 없습니다. 만약 정수 배열의 최대 길이가 10이라면 0(N2)알고리즘을 사용해도 되죠. 제가 이 문제를 제시한 이유는 제약 조건에 따른 알고리즘의 선택을 보여주기 위함입니다. 이렇게 제약 조건에 따라 같은 문제도 난이도가 달라질 수 있습니다. 그리고 이런 때에 초보자가 하기 쉬운 실수는 너무 문제가 쉽다고 생각해서 제약 조건을 고려하지 않는다는 겁니다. 단순히 내림차순 또는 오름차순으로 정렬하면 이 문제는 통과할 수 없습니다. 정답 코드는 다음과 같이 짧습니다.

pricate static int[] solution(int[] arr){
    Array.sort(arr);
    return arr;
}

'Java' 카테고리의 다른 글

MapReduce Architecture  (0) 2023.11.27