[코딩 테스트 Java] 배열 ❶에서는 배열 개념과 ArrayList 사용 방법을 알아보았습니다. 이제 배열 관련 몸풀기 문제를 풀면서 배열 공부를 마무리하겠습니다. 저자 선생님이 직접 만든 개념 확인 문제입니다. 깃허브 코드를 확인해주세요.
문제 01 배열 정렬하기 ⭐️
- 저자 권장 시간_10분
- 권장 시간 복잡도_O(NlogN)
- 출제_저자 출제
- 정답 URL_ https://github.com/retrogemHK/codingtest_java/blob/main/solution/01.java
정수 배열을 정렬해서 반환하는 solution( ) 함수를 완성하세요.
제약 조건
- 정수 배열의 길이는 2 이상 105 이하입니다.
- 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.
입출력의 예
문제 분석하고 풀기
문제만 놓고 보면 간단해 보이지만 제약 조건은 주의 깊게 봐야 합니다. 제약 조건을 보면 데이터 개수는 최대 105입니다. 즉, 제한 시간이 3초라면 O(N2) 알고리즘은 사용할 수 없습니다. 만약 정수 배열의 최대 길이가 10이라면 O(N2) 알고리즘을 사용해도 되죠. 제가 이 문제를 제시한 이유는 제약 조건에 따른 알고리즘의 선택을 보여주기 위함입니다. 이렇게 제약 조건에 따라 같은 문제도 난이도가 달라질 수 있습니다. 그리고 이런 때에 초보자가 하기 쉬운 실수는 너무 문제가 쉽다고 생각해서 제약 조건을 고려하지 않는다는 겁니다. 단순히 내림차순 또는 오름차순으로 정렬하면 이 문제는 통과할 수 없습니다. 정답 코드는 다음과 같이 아주 짧습니다.
private static int[] solution(int[] arr) {
Arrays.sort(arr);
return arr;
}
Arrays.sort( ) 메서드는 배열을 오름차순으로 정렬합니다. 주목할 점은 sort( ) 메서드가 원본 배열 자체를 정렬시킨다는 것입니다. 만약 원본 배열을 그대로 두고 싶다면 다음과 같이 구현하면 됩니다.
private static int[] solution(int[] arr) {
int[] clone = arr.clone();
Arrays.sort(clone);
return clone;
}
배열의 clone( ) 메서드는 타겟이 되는 배열을 복사하여 새로운 배열로 생성합니다. 다음 두 코드의 실행 결과 차이를 보면 clone( ) 메서드가 어떻게 동작하는지 조금 더 명확하게 알 수 있습니다.
// clone() 메서드를 사용하여 배열을 복사한 경우
public static void main(String[] args) {
int[] org = {4, 2, 3, 1, 5};
int[] sorted = solution(org);
System.out.println(Arrays.toString(org)); // [4, 2, 3, 1, 5]
System.out.println(Arrays.toString(sorted)); // [1, 2, 3, 4, 5]
}
private static int[] solution(int[] arr) {
int[] clone = arr.clone();
Arrays.sort(clone);
return clone;
}
// clone( ) 메서드를 사용하지 않고 원본 배열을 수정한 경우
public static void main(String[] args) {
int[] org = {4, 2, 3, 1, 5};
int[] sorted = solution(org);
System.out.println(Arrays.toString(org)); // [1, 2, 3, 4, 5]
System.out.println(Arrays.toString(sorted)); // [1, 2, 3, 4, 5]
}
private static int[] solution(int[] arr) {
int[] clone = arr;
Arrays.sort(clone);
return clone;
}
원본 배열을 그대로 수정한 코드는 org의 출력값이 초깃값 [4, 2, 3, 1, 5]가 아니라 [1, 2, 3, 4, 5]로 바뀌어 있습니다. 참조값이 solution( ) 메서드로 넘어가 원본을 수정한 것입니다. 원본 배열의 상태를 유지하면서 원본 배열로부터 새로운 배열을 복사해서 사용해야 되는 상황에서는 clone( ) 메서드를 사용해주세요.
💡합격 조언_sort( ) 메서드를 사용하지 않고 O(N2) 알고리즘을 사용하면?
sort( ) 메서드를 사용하지 않고 O(N2) 알고리즘으로 배열 원소를 정렬하는 연산을 구현하면 시간 차이는 얼마나 벌어질까요? 다음 코드를 봅시다.
import java.util.Arrays;
class Solution {
public static void main(String[] args) {
int[] arr = new int[100000];
long start = System.currentTimeMillis();
int[] bubble = bubbleSort(arr);
long end = System.currentTimeMillis();
// Bubble 정렬 코드 시간 측정
// 1.008초
System.out.println((end - start) / 1000.0 + "초");
start = System.currentTimeMillis();
int[] sort = doSort(arr);
end = System.currentTimeMillis();
// 정렬 API 코드 시간 측정
// 0.001초
System.out.println((end - start) / 1000.0 + "초");
// 두 개의 배열이 같은지 확인
System.out.println(Arrays.equals(bubble, sort)); // true
}
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 tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
private static int[] doSort(int[] org) {
int[] arr = org.clone();
Arrays.sort(arr);
return arr;
}
}
첫 번째 방법은 O(N2) 정렬 알고리즘인 버블 정렬을 활용한 방법이고, 두 번째 방법은 O(NlogN) 시간 복잡도를 가진 sort( ) API를 활용한 방법입니다. 결과를 보면 시간 차이가 상당히 납니다. 데이터 100,000개를 오름차순으로 정렬하는 데 버블 정렬은 1초가 걸렸지만 두 번째 방법은 0.1초도 걸리지 않았습니다. 실행 환경마다 시간의 차이는 조금 생길 수 있겠지만 압도적으로 sort( ) API가 성능이 좋다는 것을 알 수 있습니다. 이것으로 알고리즘의 시간 복잡도가 얼마나 중요한지 알아두기 바랍니다. 참고로 sort( ) API의 정렬 알고리즘은 Dual-Pivot QuickSort 혹은 Tim-Sort입니다.
시간 복잡도 분석하기
N은 arr의 길이이므로 시간 복잡도는 O(NlogN)입니다.
문제 01 배열 제어하기 ⭐️⭐️
- 저자 권장 시간_10분
- 권장 시간 복잡도_O(NlogN)
- 출제_저자 출제
- 정답 URL_https://github.com/retrogemHK/codingtest_java/blob/main/solution/02.java
정수 배열을 하나 받습니다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution( ) 함수를 구현하세요.
제약 조건
- 배열 길이는 2 이상 1,000 이하입니다.
- 각 배열의 데이터 값은 -100,000 이상 100,000 이하입니다.
입출력의 예
문제 분석하고 풀기
이런 문제를 보면 직접 코드를 구현하고 싶은 마음이 들 수도 있지만 자바에서는 미리 구현된 좋은 메서드들이 많으므로 그런 메서드들도 활용해보면 좋습니다. 이 문제가 딱 그렇게 풀었을 때 좋은 문제입니다. 코드를 살펴봅시다.
import java.util.Arrays;
import java.util.Collections;
class Solution {
private static int[] solution(int[] arr) {
// ❶ 중복값 제거
Integer[] result = Arrays.stream(arr).boxed().distinct().
toArray(Integer[]::new);
Arrays.sort(result, Collections.reverseOrder()); // ❷ 내림차순 정렬
// int형 배열로 변경 후 반환
return Arrays.stream(result).mapToInt(Integer::intValue).toArray();
}
}
❶에서 Arrays 클래스의 stream( ) 메서드를 통해서 stream으로 변환합니다. 해당 stream의 프리미티브 타입인 IntStream의 데이터를 boxed( )를 통해 레퍼런스 타입인 Integer로 변환하고, distinct( ) 메서드를 통해 중복을 제거합니다. 마지막으로 Integer형 배열로 중복 제거된 데이터를 반환합니다.
가끔 자바의 표준 API를 통해 해결할 수 있는 문제를 굳이 직접 코드를 작성해서 해결하려는 경우가 있습니다. 하지만 그럴 필요가 없습니다. 이를테면 이중 반복문을 통해 일일이 데이터를 확인해서 중복값을 확인해 제거하는 알고리즘은 시간 복잡도가 O(N2)으로 성능이 좋지 않습니다. 제가 이렇게 간단해 보이는 문제를 굳이 언급한 이유는 자바에는 코딩 테스트에 유용한 표준 API들이 많고, 굳이 직접 작성하려 하지 마라를 강조하기 위함입니다. 심지어 distinct( ) 메서드는 시간 복잡도 O(N)을 보장합니다.
또한 ➋의 Arrays.sort( ) 메서드 활용하는 부분을 보면 내림차순 정렬을 하기 위해 Collections.reverseOrder( )를 인수로 넘겼습니다. 인수가 없으면 기본값은 오름차순입니다. 마지막으로 Integer[ ] 형태의 배열을 int[ ] 형태로 변환하여 반환합니다.
💡합격 조언_자바의 스트림
자바에서 스트림(Stream)은 데이터의 흐름입니다. 스트림은 데이터의 소스를 추상화하고 데이터를 다루는데 유용한 메서드를 정의해 놓은 것입니다. 다시 말해 배열 또는 컬렉션을 스트림으로 변환하면 for문 등의 반복문을 사용하지 않고도 컬렉션의 데이터를 배열에 담아서 반환하거나 특정 조건에 따라 필터링하는 등 코드의 양을 줄이고 가독성을 향상시킬 수 있습니다. 다만 이것은 개발 관점에서의 이야기입니다. 코딩 테스트 관점에서는 시간 복잡도 측면에서 for문 등의 반복문과 스트림은 성능에 큰 차이가 없습니다. 다시 말해 스트림을 쓰나 for문과 같은 반복문을 쓰나 코드의 수행 시간이 향상되지는 않습니다. 따라서 스트림 사용에 익숙하지 않다면 for문과 같은 반복문을 사용해도 됩니다.
다만 앞에서 언급했듯이 효율성이 떨어지는 상황에는 가급적 표준 API를 사용해서 시간 초과가 발생하지 않도록 하는 것이 중요합니다. 스트림을 사용해서 O(N)에 해결할 수 있는 문제를 for문과 같은 반복문으로(O(N)으로) 해결하는 건 크게 문제가 되지 않지만 distinct( ) 메서드를 사용하지 않고 반복문 등을 이용하여 직접 구현한 O(N2)으로 풀면 시간 초과가 발생할 수도 있다는 뜻입니다. distinct( ) 메서드의 기능을 컬렉션 프레임워크의 Set으로 구현하는 건 코딩 테스트 관점에서는 시간 복잡도가 O(N)이므로 문제가 되지는 않습니다. 만약 스트림 없이 앞에서 본 코드를 다시 구현한다면 다음과 같이 정렬과 중복 제거를 동시에 할 수 있는 TreeSet을 사용해 O(NlogN)으로 구현할 수 있습니다.
import java.util.Collections;
import java.util.TreeSet;
public class Solution {
private static int[] solution(int[] arr) {
// ❶ 중복값 제거, ❷ 내림차순 정렬
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;
}
}
시간 복잡도 분석하기
N은 arr의 길이입니다. arr의 중복 원소를 제거하는 데 걸리는 시간 복잡도는 O(N)이고, 이를 다시 정렬하는 데 걸리는 시간 복잡도는 O(NlogN)이므로 최종 시간 복잡도는 O(NlogN)입니다.
자료구조, 알고리즘, 빈출 97 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(자바 편)
저자 김희성
현 42dot 백엔드 개발자. 이전에는 삼성SDS에서 소프트웨어 개발자, 쿠팡에서 풀스택 개발자로 근무했다. 특히 삼성SDS 시절에는 사내 SW역량테스트 강사로 활약했다. 귀찮은 거 싫어하고 집에서 자는 게 가장 좋은 백엔드 개발자다. 어려운 문제와 맞닥뜨렸을 때 더욱 불타오르는 타입. 새벽 시간에 코드짜는 걸 좋아하며 주말에 밤새 코딩하는 일을 즐기는 ESTJ.
