02-1. 배열 몸풀기 문제

코딩테스트를 준비하면서 가장 기본이 되는 자료구조는 배열(Array)이다.
배열 문제에서는 보통 다음 3가지 패턴이 자주 등장한다.

• 배열 정렬
• 중복 제거
• 배열 ↔ 리스트 변환

---

1️⃣ 배열 정렬하기

정수 배열을 정렬해서 반환하는 solution() 함수를 작성한다.

import java.util.Arrays;

public class Main {

    private static int[] solution(int[] arr) {
        Arrays.sort(arr); // 오름차순 정렬
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1};
        int[] sorted = solution(arr);

        System.out.println(Arrays.toString(sorted));
        // [1, 2, 5, 9]
    }
}

 

---

Arrays.sort()

Arrays.sort(arr);

특징

• 배열을 오름차순으로 정렬
• 원본 배열 자체가 변경됨 (in-place 정렬)

시간복잡도

O(n log n)

---

원본 배열 유지 방법

정렬 시 원본 배열을 유지하고 싶다면 복사 후 정렬을 사용한다.

int[] copy = arr.clone();
Arrays.sort(copy);

또는

int[] copy = Arrays.copyOf(arr, arr.length);

---

2️⃣ 배열 제어하기

정수 배열을 받아 중복값 제거 -> 내림차순 정렬 한 뒤 반환하는 문제

 

✔ 내가 작성한 풀이

import java.util.*;

public class Main {

    private static int[] solution(int[] arr) {

        Arrays.sort(arr); // 오름차순 정렬

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

        // 중복 제거
        int prev = arr[0];
        list.add(prev);

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != prev) {
                list.add(arr[i]);
                prev = arr[i];
            }
        }

        // 내림차순 정렬
        Collections.sort(list, Collections.reverseOrder());

        // List → int[] 변환
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 2, 5, 1};
        int[] sorted = solution(arr);

        System.out.println(Arrays.toString(sorted));
        // [9, 5, 2, 1]
    }
}

---

[풀이 과정]

 

1. 배열 정렬

배열을 오름차순 정렬한다.

Arrays.sort(arr);

[5,2,9,2,5,1]
→
[1,2,2,5,5,9]

 

2. 중복 제거

int prev = arr[0];
list.add(prev);

이전 값을 저장하고 다를 경우만 추가한다.

if(arr[i] != prev)
// [1,2,2,5,5,9] → [1,2,5,9]

 

3. 내림차순 정렬

Collections.sort(list, Collections.reverseOrder());

Collections.reverseOrder()

• 이 메서드는 내림차순 정렬 기준(Comparator)을 반환한다.
• 내부적으로 큰 값 → 작은 값 순서로 정렬
• 기본형 배열에서는 사용할 수 없어 boxed() 해줘야 함 

실제 동작 과정

1. Arrays.sort() 실행
2. Comparator로 reverseOrder 사용
3. 큰 값이 앞으로 오도록 비교
4. 배열을 내림차순 정렬

 

4. List → 배열 변환

list.stream().mapToInt(Integer::intValue).toArray();

---

✔ 책 풀이 (Stream API)

import java.util.Arrays;
import java.util.Collections;

public class Main {

    private static int[] solution(int[] arr) {

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

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

        return Arrays.stream(res)
                .mapToInt(Integer::intValue)
                .toArray();
    }
}

---

Stream API 주요 메서드

boxed() : 기본형 → 참조형 변환

- Comparator는 기본형 배열에 사용할 수 없음

int → Integer

 

distinct() : 중복 제거

---

 

for문 vs Stream

for문	직접 제어 가능, 알고리즘 이해 쉬움
Stream	코드 간결, 선언형 프로그래밍

 

---

📌 정리

1. 배열 정렬

Arrays.sort(arr); // 오름차순
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순

시간복잡도

O(n log n)

 

2. 중복 제거 방법

1. Set 사용
2. distinct()
3. 직접 비교

 

3. List ↔ 배열 변환

List → 배열

list.stream().mapToInt(Integer::intValue).toArray();

배열 → List

Arrays.stream(arr).boxed().toList();