코딩테스트 배열 관련 함수

1. 정렬 Arrays.sort()

1)배열을 오름차순으로 정렬

2)기본 오름차순

다른 정렬 기준: Comparator 인터페이스 구현

int[] arr = {3, 1, 4, 1, 5, 9};
Arrays.sort(arr);
// [1, 1, 3, 4, 5, 9]

 

내림차순 정렬

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

 

3)객체 배열 정렬하기

String[] fruits = {"Pineapple", "Apple", "Orange", "Banana"};
Arrays.sort(fruits);
//알파벳 순으로 정렬

Comparable, Comparator 인터페이스: 객체 정렬 기준

(1)Comparable 인터페이스

구현시 compareTo 메서드 오버라이드 필요: 현재 객체와 매개변수로 받은 객체를 비교해서 정렬 순서 결정

현재 객체가 매개변수 객체보다 작으면 -1, 같으면 0, 크면 1 반환

class Person implements Comparable<Person> {
    private String name;
    public Person(String name) {
        this.name = name;
    }
    public String getName() {
        return name;
    }
    @Override
    public int compareTo(Person other) {
    	//객체의 name 변수끼리 비교
        return this.name.compareTo(other.name);
    }
}

Person[] people = {new Person("John"), new Person("Alice"), new Person("Bob")};
//객체의 name 변수 기준으로 정렬
Arrays.sort(people);

 

(2)Comparator 인터페이스

두 객체를 비교하는 compare 메서드 정의

정렬 기준을 객체의 정의와 독립적으로 제공

같은 객체에 여러 가지 정렬 기준 제공 가능

매개변수1이 매개변수2보다 작으면 -1, 같으면 0, 크면 1 반환

class Person {
    private String name;
    private int age;
    // 생성자, getter, setter 생략
}

Person[] people = {new Person("John", 25), new Person("Alice", 20), new Person("Bob", 22)};
Arrays.sort(people, new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getAge(), p2.getAge());
    }
});

//람다식 사용
Arrays.sort(people, (p1, p2) -> Integer.compare(p1.getAge(), p2.getAge()));

 

4)시간 복잡도

보통 O(NlogN)

 

 

 

2. 중복 제거

1)distinct()

stream API의 메서드

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

 

Arrays.stream(arr): arr 배열로부터 스트림 생성

- 시간복잡도 O(N)

boxed(): 기본 자료형 스트림을 해당 래퍼 클래스의 스트림으로 변환(Integer)

- 시간복잡도 O(N)

distinct(): equals() 메서드로 스트림에서 중복된 요소 제거

- 시간복잡도 O(N)

toArray(Integer[]::new): 수정된 스트림을 Integer 배열로 변환

- 시간복잡도 O(N)

::
메서드 참조(Method Reference)
람다 표현식의 한 형태
특정 메서드를 직접 참조해서 해당 메서드의 실행을 나타낼 때 사용

Integer[]::new
생성자 참조(Constructor Reference)
Integer[] 타입의 새 배열을 생성하는 생성자 참조

->스트림의 요소들을 포함하는 새로운 Integer[] 배열 생성
length를 인자로 받아 new Integer[length]를 수행하는 생성자의 참조와 같음

 

2)HashSet 사용

HashSet에 저장된 값을 오름차순으로 정렬하고 int[] 배열로 반환하기

HashSet<Integer> set = new HashSet<>();

//HashSet에 값 입력

set.stream().sorted().mapToInt(Integer::intValue).toArray();

stream(): 스트림 생성

- 시간복잡도 O(N)

sorted(): 스트림을 오름차순으로 정렬

- 시간복잡도 O(NlogN)

mapToInt(Integer::intValue): 각 Integer 객체를 int 값으로 변환

- Integer 객체의 intValue 메서드 호출, Integer 객체를 int 타입으로 변환

- 람다식 사용시 mapToInt(x -> x)

- 시간복잡도 O(N)

toArray(): int 스트림을 배열로 변환

- 시간복잡도 O(N)

->O(NlogN)