1. 서론
프로그래밍 입문자 및 개발자 지망생들에게 배열과 리스트는 기본적인 자료구조입니다. 이 두 가지 자료구조를 이해하는 것은 다양한 코딩테스트 문제에서 뛰어난 성능을 발휘하기 위해 매우 중요합니다. 이 글에서는 자바를 사용하여 배열과 리스트를 활용한 알고리즘 문제를 하나 풀어보겠습니다.
2. 문제 설명
문제: 주어진 정수 배열에서 중복된 요소를 제거하고, 남은 요소들을 정렬하여 반환하는 메소드를 작성하시오. 결과 배열은 오름차순으로 정렬되어야 하며, 중복 값은 제거되어야 합니다.
문제 요약
- 입력: 정수 배열
- 출력: 중복을 제거한 후 오름차순으로 정렬된 배열
3. 예제
입력: [3, 1, 2, 3, 4, 2, 1]
출력: [1, 2, 3, 4]
4. 접근 방식
이 문제를 해결하기 위해 우리는 다음과 같은 단계를 따를 것입니다:
- 단계 1: 입력 배열에서 중복된 요소를 제거합니다.
- 단계 2: 남은 요소들을 정렬합니다.
- 단계 3: 최종 결과를 반환합니다.
5. 코드 구현
이제 위의 접근 방식을 바탕으로 자바 코드를 작성해 보겠습니다.
import java.util.Arrays;
import java.util.HashSet;
public class RemoveDuplicatesAndSort {
public static int[] removeDuplicatesAndSort(int[] arr) {
// HashSet을 사용하여 중복 제거
HashSet set = new HashSet<>();
for (int num : arr) {
set.add(num);
}
// 중복 제거한 요소를 배열로 변환
int[] uniqueArray = new int[set.size()];
int index = 0;
for (int num : set) {
uniqueArray[index++] = num;
}
// 배열 정렬
Arrays.sort(uniqueArray);
return uniqueArray;
}
public static void main(String[] args) {
int[] input = {3, 1, 2, 3, 4, 2, 1};
int[] result = removeDuplicatesAndSort(input);
System.out.println(Arrays.toString(result)); // [1, 2, 3, 4]
}
}
코드 설명
위 코드는 removeDuplicatesAndSort라는 메소드를 정의하고 있습니다. 이 메소드는 입력 배열에서 중복된 요소를 제거하고 정렬된 배열을 반환합니다.
- 우선
HashSet을 사용하여 중복된 정수들을 간단히 제거합니다. - 그리고
HashSet의 내용을 새로운 배열로 복사합니다. - 마지막으로
Arrays.sort를 사용하여 배열을 정렬합니다.
6. 복잡도 분석
이 알고리즘의 시간 복잡도는 다음과 같습니다:
- 중복 제거: O(n), 여기서
n은 입력 배열의 크기입니다. - 정렬: O(m log m), 여기서
m은 중복 제거된 배열의 크기입니다.
따라서 전체 시간 복잡도는 O(n + m log m)입니다.
7. 결론
이번 강좌에서는 자바를 사용하여 배열과 리스트를 활용한 중복 제거 및 정렬 알고리즘을 구현해 보았습니다. 각 단계를 통해 기본적인 자료구조의 작동 방식을 이해하고, 실력을 키워나가는 방법을 배웠습니다. 앞으로도 다양한 알고리즘 문제를 해결하면서 더 많은 경험을 쌓아가길 바랍니다.
참고 문헌
- 자료구조 및 알고리즘 관련 서적
- Java 공식 문서
8. 추가 연습 문제
다음과 같은 문제를 추가로 시도해 보세요.
- 정렬된 배열이 주어졌을 때, 중복된 값을 제거하고 새로운 배열을 반환하는 메소드를 구현하시오.
코딩 연습을 통해 알고리즘 이해도를 높이고, 실력을 쌓으세요!