배열

선언

int[] arr = {0,0,0,0,0,0};
int[] arr = new int[6];

• ArrayList - 저장할 데이터 개수를 정확히 알 수 없다면…

차원

• 2차원

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

ArrayList

• 추가

ArrayList<Integer> list = new ArrayList<>();
list.add(1);

• 초기화

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

• 접근 - get(index)
• 삭제 - remove()

• length 변수
• Arrays.sort()
• toString()
• size()
• isEmpty()
• Collections.sort

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
Collections.sort(list); // array는 Arrays.sort()

• sort() 사용시 from 인덱스, to 인덱스로 특정범위만 정렬 가능

ArrayList 효율성

• 시간 복잡도

• 접근 O(1)
• 맨 뒤 삽입 O(1)
• 맨 앞이나 중간. O(N)

• 고려할 점
  • 할당할 수 있는 메모리 - 정수형 1차원 1000만개, 2차원은 3000*3000 정도
  • 중간에 데이터 삽입이 빈번한 경우 시간 초과할 수 있음.

몸풀기 문제

정렬

• Arrays.sort() -> Dual-Pivot QuickSort 혹은 Tim-Sort : 성능좋으니까 그냥 쓰자

// bubble sort 예
private static int[] bubbleSort(int[] org) {
    int[] arr = org.clone();
    int n = arr.length;
    for(int i=0; i< n; i++) {
        for(int j=0; j<n-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

• 원본을 그대로 두고 싶으면

int[] clone = arr.clone();

배열 제어하기

• 중복 제거

Integer[] result = Arrays.stream(arr).boxed().distinct().toArray(Integer[]::new);

Arrays.sort(result, Collections.reverseOrder()); 

Arrays.stream(result).mapToInt(Integer::intValue).toArray(); // int[]로

• 가급적 표준 API를 사용해서 시간초과 발생하지 않도록

TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
int[] result = new int[set.size()];
for(int i = 0; i < result.length; i++) {
    result[i] = set.pollFirst();
} 
// 중복제거 O(N), 정렬 O(NlogN) => O(NlogN)