[코딩테스트합격자되기-자바편] 문제02. 배열 제어하기

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

내용

정수 배열을 하나 바습니다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution() 함수를 구현하세요.

 

제약조건

• 배열의 길이는 2이상 1,000 이하
• 각 배열의 데이터 값은 -100,000 이상 100,000 이하

 

입출력의 예

입력	출력
[4, 2, 2, 1, 3, 4]	[4, 3, 2, 1]
[2, 1, 1, 3, 2, 5, 4]	[5, 4, 3, 2, 1]

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

1. 중복값 제거를 먼저하자.
2. 그런 뒤 내림차순으로 정렬하자.

 

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
16:50	17:06	16분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

• 배열의 길이는 2이상 1,000 이하입니다.
• 각 배열의 데이터 값은 -100,000 이상 100,000 이하입니다.

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

입력	출력
[4, 2, 2, 1, 3, 4]	[4, 3, 2, 1]
[2, 1, 1, 3, 2, 5, 4]	[5, 4, 3, 2, 1]

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(정수형배열) {
    // 1. 중복값_없애기
    // 2. 내림차순_정렬하기
    return 정수형배열
}

 

구현

import java.util.Arrays;  
import java.util.Comparator;

public static int[] solution(int[] arr) {  
    return Arrays.stream(arr).boxed()  
            .distinct() // 1. 중복값 없애기
            .sorted(Comparator.reverseOrder()) // 2. 내림차순 정렬하기
            .mapToInt(Integer::intValue)  
            .toArray();  
}

 

 

복기하기

답안과 나의 풀이를 비교해보세요

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

public static int[] solution(int[] arr) {  
    // 1. 중복값 제거
    Integer[] result = Arrays.stream(arr).boxed().distinct().toArray(Integer::new);
    Arrays.sort(result, Collections.reverseOrder()); // 2. 내림차순 정렬
    // int형 배열로 변경 후 반환
    return Arrays.stream(result).mapToInt(Integer::intValue).toArray();
}

• 장점
  • 각 단계가 명확하게 구분되어 있어 주석과 함께 이해하기 쉽습니다
• 단점
  • 중간 배열(result)을 생성하므로 추가적인 메모리를 사용합니다
  • 스트림을 두 번 생성하므로 성능상 불리할 수 있습니다

 

AI 에게 질문: .sorted(Comparator.reverseOrder()) 이거랑 Arrays.sort(result, Collections.reverseOrder()); 둘 중에 뭐가 나아?

 

.sorted(Comparator.reverseOrder())

• 스트림 연산의 일부로 실행됩니다
• 새로운 스트림을 생성합니다
• 원본 데이터는 변경되지 않습니다 (불변성 유지)
• 다른 스트림 연산들과 함께 파이프라인으로 처리되므로 전체적인 흐름이 자연스럽습니다

 

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

• 기존 배열을 직접 정렬합니다 (in-place sorting)
• 추가 메모리 공간이 거의 필요하지 않습니다
• 원본 데이터가 변경됩니다
• 정렬만 수행하는 경우 이 방식이 더 효율적일 수 있습니다

 

이 경우에는 .sorted(Comparator.reverseOrder())가 더 좋은 선택입니다.
그 이유는:

1. 전체 작업이 스트림으로 처리되고 있어서, 스트림 파이프라인의 일부로 자연스럽게 들어맞습니다
2. 다른 변환 작업들(boxed, distinct, mapToInt)과 함께 일관된 방식으로 처리됩니다
3. 코드의 가독성이 더 좋습니다

 

만약 단순히 배열 정렬만 필요한 상황이었다면 Arrays.sort()가 더 효율적일 수 있지만, 이 경우처럼 여러 변환 작업이 함께 있는 경우에는 스트림의 .sorted()를 사용하는 것이 더 적절합니다.

 

 

TreeSet을 사용해 O(NlogN)으로 구현하기

import java.util.Collections;
import java.util.TreeSet;

public static int[] solution(int[] arr) {
    // 1. 내림차순 정렬 - 시간 복잡도: O(NlogN)
    // 2.중복값 제거 - 시간 복잡도 - 시간 복잡도: O(N)
    TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
    for (int num: arr) {
        set.add(num);
    }

    // int형배열에 담아서 반환
    int[] result = new int[set.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = set.pollFirst();
    }
    return result;
}

 

 

요약하기

• 자바에는 코딩 테스트에 유용한 표준 API들이 많아 굳이 직접 작성하지 않아도 된다.
• distinct() 메서드는 시간 복잡도 O(N)을 보장한다.

 

자바의 스트림

• 자바에서 스트림(stream)은 데이터의 흐름이다.
• 데이터의 소스를 추상화하고 데이터를 다루는데 유용한 메서드를 정의해놓은 것이다.
• 코딩 테스트 관점에서는 시간 복잡도 측면에서 for문 등의 반복문과 스트림은 성능에 큰 차이가 없다.
• 효율성이 떨어지는 상황에서는 가급적 표준 API를 사용해서 시간 초과가 발생하지 않도록 하는 것이 중요하다.