글 읽기 - 병합정렬 질문

sonbe8704 3년 전 0

이해는 했는데 다른코드들 찾아봐도 똑같은거같은데 뭐가 다른지 모르겠습니다.

#include<iostream>
#include<map>
using namespace std;
int arr[500001];
int original[500001];
int temp[500001];
int N;
int cnt;
void merge(int left, int mid, int right) {
	int i = left, k = mid + 1, j = left;
	while (i <= mid && k <= right) {
		if (arr[i] < arr[j])
			temp[j++] = arr[i++];
		else {
			temp[j++] = arr[k++];
			cnt += mid - i + 1;
		}
	}
	while (i <= mid)temp[j++] = arr[i++];
	while (j <= right)temp[j++] = arr[k++];
	for (int i = left; i <= right; i++) {
		arr[i] = temp[i];
	}
}
void divide(int left, int right) {
	if (left >= right)return;
	int mid = (left + right) / 2;
	divide(left, mid);
	divide(mid + 1, right);
	merge(left,mid, right);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int sum = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	divide(0,N-1);

	cout << cnt << "\n";
}

dldyddlwl 3년 전 1

아래에 있습니다.

long long cnt; // 답이 int형 범위를 넘어설 수 있음

// 11번 라인
while (i <= mid && k <= right) {
	if (arr[i] < arr[j])        // arr[i]와 arr[j]의 비교가 아닌, arr[i]와 arr[k] 간의 비교가 옳음
			temp[j++] = arr[i++];    // 또한 숫자가 같은 경우는 swap이 일어날 필요가 없음
	else {                            // 따라서, arr[i] <= arr[j] 그리고 else문의 조건이 옳음
			temp[j++] = arr[k++];
			cnt += mid - i + 1;
		}
	}

sonbe8704 3년 전 0

감사합니다

항상 이런 사소한부분을 놓치지 않으려하는데 안보이는날은 진짜 안보이더라고요...

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

병합정렬 질문

sonbe8704 3년 전 0

dldyddlwl 3년 전 1

sonbe8704 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말