[프로그래머스][C++] 중앙값 구하기
중앙값 구하기
문제 링크
분석
배열을 정렬하고 배열의 중앙값(중간 인덱스의 값)을 반환하는 문제입니다.
이 문제에서 배열의 크기가 항상 홀수이므로 중앙값을 정확히 하나로 정의할 수 있습니다.
정렬은 STL의 sort()함수를 사용하지 않고, 직접 구현해서 정렬해보겠습니다.
선택 정렬, 버블 정렬의 시간복잡도는 $O(N^2)$이며, 삽입 정렬의 경우 $O(N)$가 최선으로 해당 문제에서 10초를 초과해 실행이 중단됩니다.
그러므로 이 문제에서는 병합 정렬을 사용하겠습니다.
병합 정렬은 배열을 반으로 분할해 재귀적으로 정렬한 뒤 병합하는 알고리즘입니다.
시간 복잡도는 $O(N \log N)으로, 큰 데이터를 효율적으로 처리할 수 있습니다.
풀이
#include <vector>
void merge(std::vector<int>& array, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i)
{
L[i] = array[left + i];
}
for (int j = 0; j < n2; ++j)
{
R[j] = array[mid + j + 1];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
array[k++] = L[i++];
}
else
{
array[k++] = R[j++];
}
}
while (i < n1)
{
array[k++] = L[i++];
}
while (j < n2)
{
array[k++] = R[j++];
}
}
void mergeSort(std::vector<int>& array, int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
int solution(std::vector<int> array) {
int answer{};
mergeSort(array, 0, array.size() - 1);
answer = array[array.size() / 2];
return answer;
}
실행 순서대로 설명하도록 하겠습니다.
우선 간단한 설명입니다.
solution함수
mergeSort를 호출해 배열을 정렬합니다.
매개변수로 배열array, 첫 번째 인덱스 0, 마지막 인덱스 array.size() - 1을 전달합니다.
정렬이 끝난 후 배열의 중앙값을 반환합니다.
mergeSort함수
배열을 절반으로 나누고, 다시 mergeSort를 호출합니다.(왼쪽, 오른쪽 배열)
배열이 더 이상 나뉠 수 없을 때(left >= right), merge함수를 호출해 병합합니다.
merge함수
왼쪽, 오른쪽 배열을 각각 복사합니다.
두 배열의 값을 비교하며 정렬된 순서로 원본 배열에 병합합니다.
한쪽 배열에 값이 남아있다면, 이를 모두 원본 배열에 추가합니다.
다음은 자세한 설명입니다.
solution함수에서 mergeSort함수를 호출합니다.
이때 정렬하려는 array배열을 매개변수로 넘겨줍니다.
배열의 첫번째 인덱스부터 정렬하려하므로 0을 넘겨줍니다.
배열의 마지막까지 정렬할 것이므로 마지막 인덱스인 array.size() - 1를 넘겨줍니다.
이때 array.size함수는 배열의 크기를 반환하므로 범위를 넘겨주기 위해 -1을 합니다.
예시로 배열의 크기가 5라면 배열 안에는 [0, 1, 2, 3, 4] 이렇게 5개의 변수가 있을 수있고, 마지막 인덱스는 4입니다.
그럼 mergeSort함수에서는 배열을 절반씩 나누고 합치는 함수인 merge를 호출합니다. 그 과정은 다음과 같습니다.
우선 배열을 절반으로 나누기 위해 int mid = left + (right - left) / 2로 중간 인덱스를 계산합니다.
(right - left)는 배열의 범위를 나타냅니다.
여기에 /2를 하면 범위의 중간 인덱스가 나오지만, 아직 시작 위치를 반영하지 않은 값이므로 left를 더해 시작 위치를 반영합니다.
처음부터 (left + right) / 2를 사용하면 오버플로우가 발생할 수 있기 때문입니다.
해당 문제에서는 오버플로우는 발생하지 않지만, 다양한 환경에서 안정적으로 작동하는 코드를 연습하기 위해 사용했습니다.
이후에 mergeSort함수를 두번 호출하는 이유는 병합 정렬은 우선 배열의 크기가 2 혹은 1이 될때까지 나누어야 하기 때문입니다.
절반으로 나누므로, 절반의 왼쪽 배열, 절반의 오른쪽 배열에 대해 각각 함수를 재귀적으로 호출합니다.
이때 절반으로 나눈다는 이야기는 array변수를 수정하거나 새로운 변수를 만드는것이 아닌 접근하는 범위에 대해 개념적으로 분리를 하는것입니다.
그럼 반복적으로 배열을 더이상 나눌 필요가 없다는 것을 확인해야하는데, 그 작업은 if (left < right)가 해줍니다.
배열이 절반씩 나눠져 크기가 2 혹은 1이 됐다면, merge함수가 호출됩니다.
절반으로 나눠진 배열들에 대해 merge 함수에서 작업이 되며, 개념적으로만 분리됐던 배열이 직접적으로 수정됩니다.
int n1 = mid - left + 1;와 int n2 = right - mid;는 각각 왼쪽 배열과 오른쪽 배열의 크기를 계산한 것입니다.
n1을 계산할 때 +1을 해주는 이유는 인덱스를 포함하기 때문에 크기가 하나 커야하기 때문이고, n2는 더해주지 않아도 됩니다.
vector<int> L(n1), R(n2);는 절반으로 나눈 왼쪽 부분과 오른쪽 부분에 대한 임시 배열입니다.
바로 다음 for문은 왼쪽 부분의 배열과 오른쪽 부분의 배열에 array의 값을 복사해줍니다.
그 이유는 원본 배열을 보호하고, 각 배열을 독립적으로 정렬하고 병합하기 위함입니다.
다음 while문에서는 두 개의 정렬된 배열을 병합하는 단계입니다.
L과 R은 정렬된 상태이므로, 이를 하나의 배열로 병합하는 작업을 수행합니다.
while문의 조건은 L과 R 모두 처리할 원소가 남았는지 확인하기 위함입니다.
하지만 처리할 원소가 남았다면 두 배열에서 가장 작은 값을 하나씩 비교해 원본 배열array에 넣습니다.
원본 배열에 값을 넣을 때 k는 array의 인덱스를 관리하며 left에서 시작하는 이유는 범위의 가장 첫 인덱스이기 때문입니다.
위의 과정이 모두 끝나고 만약 한쪽이라도 처리할 원소가 남아있지 않다면 마지막 while문 2개에서 대입하고 함수는 끝납니다.
이렇게 정렬을 마치고 난 다음 가운데 값은 array가 홀수이므로 array.size() / 2연산을 해 가운데 인덱스를 찾고, 접근해 값을 반환합니다.
성능 요약
테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.02MB)
테스트 5 〉 통과 (0.01ms, 4.17MB)
테스트 6 〉 통과 (0.02ms, 4.14MB)
테스트 7 〉 통과 (0.03ms, 4.2MB)
테스트 8 〉 통과 (0.02ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
댓글남기기