[백준 1517] 버블 소트

중간에 논리오류가 발생했지만, 수정 뒤에 정상적으로 출력이 가능하다.

어디가 잘못된 건지, 곰곰히 생각해봐도 아직 모르겠지만,

중간에 바꾼건 사실

            ans += (long long)(mid - i + 1);

이 부분이 전부이긴하다.

출처 : https://www.acmicpc.net/problem/1517

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

출력

첫째 줄에 Swap 횟수를 출력한다

예제 입력 1

3
3 2 1

예제 출력 1

3

소스 코드

#include <iostream> using namespace std; #define MAX_N 500000 int n; int A[MAX_N]; int B[MAX_N]; long long solve(int start, int end) { if (start == end) return 0; int mid = (start + end) / 2; long long ans = solve(start, mid) + solve(mid + 1, end); int i = start; int j = mid + 1; int k = 0; while (i <= mid || j <= end) { if (i <= mid && (j > end || A[i] <= A[j])) { B[k++] = A[i++]; } else { // 왼쪽 배열의 남아있는 원소들의 개수 ans += (long long)(mid - i + 1); B[k++] = A[j++]; } } for (int i = start; i <= end; i++) { A[i] = B[i - start]; } return ans; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> A[i]; long long ans = solve(0, n - 1); cout << ans; return 0; }

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.