백준_1517 버블 소트 (병합정렬)Algorithm/Algorithm 문제2024. 1. 17. 13:32
Table of Contents
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_1517 {
static int[] arr, tempArr;
static long result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
tempArr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
result = 0;
mergeSort(0, n-1);
System.out.println(new StringBuilder().append(result));
}
static void mergeSort(int s, int e) {
if(e-s<1) {
return;
}
int m = (s+e)/2;
mergeSort(s, m);
mergeSort(m+1, e);
int i, j, k;
for(i=s; i<e+1; i++) {
tempArr[i] = arr[i];
}
i=s;
j=m+1;
k=s;
while(i<m+1 && j<e+1) {
if(tempArr[i] > tempArr[j]) {
result += m-i+1;
arr[k++] = tempArr[j++];
}
else {
arr[k++] = tempArr[i++];
}
}
while(i<m+1) {
arr[k++] = tempArr[i++];
}
while(j<e+1) {
arr[k++] = tempArr[j++];
}
}
}
merge sort의 정렬 과정에서 bubble sort의 swap 횟수를 알아낼 수 있다는 힌트를 얻고,
이해하고 풀었는데 계속 시간초과,, 분명 O(nlogn) 으로 가능한 문제인데.
알고보니
tempArr에 arr의 (s,e) 범위를 복붙하는 for에서
i=s로 시작했어야 할 거를 i=0으로 잘못 입력해서 그랬던 것이다.
매번 (0,e) 범위를 tempArr에 저장하려니 시간 초과하는건 당연
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_10989 수 정렬하기3 (기수정렬) - 성공(풀이 참고) (0) | 2024.01.18 |
---|---|
백준_10989 수 정렬하기 3 (기수 정렬) - 실패(메모리초과) (0) | 2024.01.18 |
백준_2751 수 정렬하기2 (풀이 참고 코드개선) (0) | 2024.01.17 |
백준_2751 수 정렬하기2 (병합정렬) (0) | 2024.01.16 |
백준_11004 k번째 수 (퀵정렬) (0) | 2024.01.15 |
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!