[알고리즘] 배열 (Java)

01. 배열

• 인덱스와 값을 일대일 대응해 관리하는 자료구조
• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근 가능

배열 선언

int[] arr = { 0, 0, 0, 0, 0, 0 };
int[] arr = new int[6];
// 둘 실행 결과 같음

• 배열은 인덱스가 0부터 시작
• 배열과 유사한 기능을 가진 ArrayList와 차이
  • 배열: 처음 선언할 때 배열의 크기 결정
    • 정확한 데이터의 개수를 알고 있는 경우 (속도 더 빠름)
  • ArrayList: 크기 동적임
    • 저장해야 할 데이터의 개수를 정확히 알 수 없는 경우

배열과 차원

• 컴퓨터 메모리의 구조는 1차원이므로 2차원, 3차원 배열도 실제로는 1차원 공간에 저장
  • 배열은 차원과는 무관하게 메모리에 연속 할당
• 1차원 배열
  • 배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당
• 2차원 배열
  • 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장

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

02. ArrayList

ArrayList<Integer> list1 = new ArrayList<>();

list.add(1);
list.add(2);
list.add(3);

// 다른 컬렉션의 데이터로 초기화
ArrayList<Integer> list2 = new ArrayList<>(list1);

// get() 메서드를 통해 데이터 접근
System.out.println(list1.get(0)); // 1

// remove() 메서드로 데이터 삭제
// 데이터를 삭제하는 위치에 따라 데이터를 복사하는 연산이 필요하므로
// 시간 복잡도가 O(N)까지 증가할 수 있으므로 주의 필요
list.remove(list.size() - 1); // 끝에 있는 데이터 삭제

(+) 배열, ArrayList 메서드

int[] arr = {1, 2, 3, 4, 5};
System.out.println(arr.length); // 5
Arrays.sort(arr); // 정렬
System.out.println(Arrays.toString(arr)); // 출력

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,4,5,3));
System.out.println(list.size());// 5
System.out.println(list.isEmpty());// false
Collections.sort(list); // 정렬
System.out.println(list) // 출력

ArrayList 효율성

• 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단번에 접근 가능
• 데이터에 접근하기 위한 시간 복잡도 = O(1)
• 데이터 추가 연산에 대한 시간 복잡도
  • 맨 뒤에 삽입
    • 데이터가 가득찬 상태에서 추가로 데이터를 또 삽입하면 리사이징(배열의 크기 늘림)
      • 50% 증가 전략 사용
      • 리사이징할 때마다 새 배열을 생성하는 것이므로 기존 데이터를 복사하는 과정 필요
        • O(N)
        • 리사이징을 자주하면 효율이 좋지 않음
        • 그렇다고 기본 사이즈를 크게 하거나 리사이징시 더 큰 크기의 배열을 생성하면 낭비 공간이 많아져 메모리 효율이 좋지 않음
      • 50% 증가 전략
        • ArrayList의 사이즈가 작을 때는 리사이징이 자주 발생하는 대신 데이터의 개수가 적어 새로운 메모리 영역에 복사하는 시간이 빠름
        • 사이즈가 클 때는 리사이징 시에 늘어나느 공간이므로 리사이징이 자주 발생하지 않는 대신 복사해야 할 데이터의 수가 많음
      • 코딩 테스트에서는 ArrayList의 리사이징으로 인한 효율성 이슈는 고려하지 않아도 될 정도로 비용이 상당히 적으니 무시해도 됨
  • 맨 앞에 삽입
    • 기존 데이터들을 뒤로 한 칸씩 밀어야 하므로 O(N)
  • 중간에 삽입
    • 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 → O(N)

배열 선택시 고려사항

• 데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능 낼 수 있음
• 메모리 공간을 충분히 확보해야 한다는 단점
• 임의 접근이라는 특징이 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있음
• 고려사항
  1. 할당할 수 있는 메모리 크기를 확인해야 함
     • 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열할당에 실패할 수 있음
     • 코딩 테스트에서는 정수형 1차원 배열은 1000만개, 2차원 배열은 3000*3000 크기를 최대로 생각해야 함
  2. 중간에 데이터 삽입이 많은지 확인해야 함
     • 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있음

배열 몸풀기 문제

01. 배열 정렬하기

Arrays.sort(arr);
return arr;

• Arrays.sort() 메서드
  • 배열을 오름차순으로 정렬
  • O(NlogN)
  • sort() 메서드는 원본 배열 자체를 정렬시킴
  • 원본 배열을 그대로 두고 싶은 경우
    • clone() 메서드
      • 타겟이 되는 배열을 복사하여 새로운 배열로 생성
  • int[] clone = arr.clone(); Arrays.sort(clone); return clone;
• 원본 배열의 상태를 유지하면서 원본 배열로부터 새로운 배열을 복사해서 사용해야 하는 상황에서는 clone() 메서드를 사용해야 함

02. 배열 제어하기

정수 배열의 중복 값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환

Integer[] result = Arrays.stream(arr).boxed().distinct().toArray(Integer[]::new);
Arrays.sort(result, Collections.reverseOrder());
return Arrays.stream(result).mapToInt(Integer::intValue).toArray();

• Arrays.stream(arr).boxed().distinct().toArray(Integer[]::new)
  • stream으로 변환
  • boxed 메서드를 통해 IntStream → Stream<Integer>
    • distinct()가 객체 비교를 해야 하므로 필요
  • distinct() 메서드를 통해 중복을 제거
    • O(N) 보장
  • toArray(Integer[]::new) → 결과를 Integer[] 타입 배열로 변환
• Arrays.sort(result, Collections.reverseOrder());
  • sort 내림차순 정렬 → O(NlogN)
• 최종 시간 복잡도 → O(NlogN)

03. 두 개 뽑아서 더하기

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution() 함수를 완성하세요.

HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < numbers.length - 1; i++) {
	for (int j = i + 1; j < numbers.length; j++) {
		set.add(numbers[i] + numbers[j]);
	}
}
return set.stream().sorted().mapToInt(Integer::intValue).toArray();

• HashSet → 중복 값을 제거한 값을 저장