코딩 테스트 _ 정렬
▤ 목차
저는 java를 주력 언어로 공부하고 있습니다. 때문에 문제 풀이 언어는 java입니다.
✍️ 개념
💡정렬 알고리즘 기본 개념
✅ 버블 정렬 (Bubble Sort)
- 두 인접한 요소를 비교해가며, 큰 값을 뒤로 보내는 방식
- 시간 복잡도: O(n²)
- 단점: 비효율적이기 때문에 큰 데이터셋에선 사용하지 않음
✅ 선택 정렬 (Selection Sort)
- 리스트에서 최소값을 찾아서 앞쪽으로 보내는 방식
- 시간 복잡도: O(n²)
- 단점: 버블 정렬과 마찬가지로 큰 데이터셋에선 비효율적
✅ 삽입 정렬 (Insertion Sort)
- 데이터를 하나씩 삽입하면서 정렬.
- 정렬된 부분에 새로운 요소를 적절히 삽입하는 방식
- 시간 복잡도: O(n²)
- 장점: 데이터가 거의 정렬되어 있으면 성능이 좋음
>> 실질적으로는 거의 정렬되어 있는지 모르기도 하고 "운에 맞겨야한다."
✅ 퀵 정렬 (Quick Sort)
- 분할 정복 알고리즘을 사용하며, 기준값(pivot)을 설정하고, 그 기준값을 기준으로 데이터를 분할하여 정렬
- 시간 복잡도: 평균 O(n log n), 최악 O(n²) (피벗 선택에 따라 달라짐)
- 장점: 평균적으로 매우 빠르고, 큰 데이터셋에 적합
✅ 병합 정렬 (Merge Sort)
- 분할 정복 알고리즘을 사용하며, 데이터를 분할하여 정렬한 후 병합
- 시간 복잡도: O(n log n)
- 장점: 최악의 경우에도 일정한 성능을 보장하고, 안정적인 정렬이 가능
✅ 힙 정렬 (Heap Sort)
- 힙 자료구조를 사용하여 정렬
- 힙을 이용하여 최대값이나 최소값을 빠르게 뽑아내는 방식
- 시간 복잡도: O(n log n)
- 장점: 안정적인 성능을 보장하지만, 다른 알고리즘보다는 구현이 조금 더 복잡
✍️ 알게된 지식 기록
💡 Arrays.sort() 반환 **
Arrays.toString(Arrays.sort(Arrays.copyOfRange(array, row[0]-1, row[1])));
문제를 풀다보니, 새로운 메모리 공간을 사용하고 싶지 않아서 짧게 쓰고싶었다.
그러다 보니 위의 코드처럼 적게 되었다.
❌ 안된다. 무엇이 문제이냐!
Arrays. sort() 메서드의 문제이다.
해당 메서드는 직접 참조하는 메서드인데 값을 반환하는게 아니고 그냥 정렬만하는 void 메서드라는 점!
> 원시타입 정렬시 퀵 정렬 알고리즘을 사용한다. (분할정복 알고리즘, 피벗에 따라 시간 복잡도가 달라짐)
> 안정성을 보장하지 않는다. 즉 순서가 중요한 경에는 다른 방법을 고려해야한다.
> 객체 배열 정렬시 내부적으로 TimSort 알고리즘 사용한다.
아.. 그냥 하나만 쓰지.. (정리해야보자)
팀정렬은 병합(Merge) 정렬 기반이다.
작은 데이터 구간에서는 삽입 정렬을 사용한다.
이미 어느정도 정렬된 배열에서 성능이 뛰어나다.
TimSort는 Python의 리스트 정렬에도 사용되고, Java의 Arrays.sort()(객체 배열)에서도 활용된다.
*****
Arrays.sort()의 구현은 정렬할 데이터 타입에 따라 달라진다.
- 원시 타입 배열 (예: int[]) -> 퀵 정렬 사용 (안정 정렬)
- 객체 배열 (예: Integer[]) -> 팀 정렬 사용 (불안정 정렬)
+
💡정적 배열에 요소 추가
크게 4가지 방법이 있는데
1. 반복문을 사용해서 기존 배열 + 1 크기로 가지는 새로운 배열을 반복 생성하여 추가하기
2. List 컬렉션을 사용해서 add해준 후 배열로 변경하기
3. System.arraycopy() 메서드 사용 (기존 배열에 +1 크기의 배열을 생성)
4. Array.copyOf() 메서드 사용 (원본 배열의 값을 복사해 새로운 배열 크기로 설)
💡.toArray[] 의 기본 반환타입은 object[]
기본적으로 컬렉션은 int[] 같은 기본형 배열을 직접 반환하지 않는다.
List 컬렉션을 사용하여 요소를 추가한 후, 배열 타입으로 변환해야한다.
문제를 거의 다 풀었다는 생각에서인지, 바로 toArray() 메서드를 사용했더니 당연히 안된다.
안될거 같긴한데 해결책은 모르겠으나 바로 아래 타입을 변환시키는게 메소드가 있는것을 확인했다.
toArray(T[] a) 잡고 찾아보니 반복을 사용하던지 stream()을 사용해야한다.
stream()을 배우기도 했고 간지나니(?) 사용했다.
+ Arrays.steam()을 사용하면 배열을 스트림으로 변환이 가능하다.
🤓결과
public int[] solution(int[] array, int[][] commands) {
int[] answer = {};
List<Integer> answerList = new ArrayList<>();
for (int[] row : commands) {
int[] subArray = Arrays.copyOfRange(array, row[0]-1, row[1]);
Arrays.sort(subArray);
answerList.add(Array.getInt(subArray, row[2]-1));
}
answer = answerList.stream().mapToInt(i->i).toArray();
return answer;
}
문제를 이런식으로 풀어서 제출했더니 제출이 되었다!
🤔 다른 사람 풀이를 보다가 ( Stream()의 속도 )
다른 사람들이 어떻게 풀었는지 보다가 나와 비슷하게 푼 문제의 댓글이 있었는데
그중 눈에 뜨인 댓글이 있었다.
스트림 API의 속도가 좋지 않다.
이런 생각은 해보지않았기에 지피티의 도움을 받았다.
!!!!!! 이 세상에 항상인건 거의 없는거 같긴 한데 , 어쨌든 반복문보다 속도가 느릴 수 있다고 한다.
처음 알게 된 사실이라 이유를 살펴보니,
1. mapToInt(i->i) 이런 변환 작업이 많아지면 (스트림 특성상) 반복자와 람다 표현식을 사용하기 때문에 오버헤드가 발생할 수 있다. (오버헤드는 추가 비용이니 - 요소)
2. 나의 경우는 List<Integer> 를 int[]로 변환하는 것. 이때 mapToInt(i ->i).toArray()를 사용하면 Integer -> int로 언박싱 과정이 추가적으로 발생하기때문에 성능 저하 발생할 수 있다.
내 나름 성능 비교 (다른 사람들은 성능 비교를 어떻게 하는지 모르겠다..) 이다.
이게 실행마다 편차가 크게 차이난다. (결과는 아래)
public static void main(String[] args) {
List<Integer> intList = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
intList.add(i);
}
// for 반복문 사용
long start = System.nanoTime();
int[] result1 = new int[intList.size()];
for (int i = 0; i < intList.size(); i++) {
result1[i] = intList.get(i);
}
long end = System.nanoTime();
System.out.println("For문 실행시간: " + (end - start) + " ns");
// Stream 사용
long start2 = System.nanoTime();
int[] result2 = intList.stream().mapToInt(i -> i).toArray();
long end2 = System.nanoTime();
System.out.println("Stream 실행시간: " + (end2 - start2) + " ns");
}
🤔 문제 풀면서 사용한 주요 개념들 (메서드)
이번에 문제를 풀면서 사용한 메서들을 몇몇개 정리하려고 한다. (아이들 도움을 많이 받았다.. 컨트롤 스페이스바 땡큐)
✅ Arrays.copyOfRange()
배열의 일부를 복사해서 새로운 배열을 생성 > O(k: 복사한 원소 개수)
✅ Array.getInt()
정렬된 배열에서 특정 인덱스 값을 가져옴. > O(1)
✅ ArrayList<Integer>
answerList.add()를 통해 정렬된 값들을 저장 > O(1) (평균), O(n) (최악, 내부 배열 크기 증가 시)
✅ stream().mapToInt(i -> i).toArray()
ArrayList<Integer> → int[] 변환 (박싱 & 언박싱 발생) > O(n)