TIL

병합정렬에 대해 공부했다.

병합정렬

배열을 반으로 나눠서 반쪽씩 정렬한 뒤 다시 붙이는 방식이다.
이 방식을 쓰면 시간 복잡도가 줄어든다고 한다..
그런데 구현이 너무 어려워서 몇번씩이고 코드를 분석하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class n24060_practice {
	static int[] tmp;
	static StringTokenizer st;
	public static void mergeSort(int[] A, int start, int end) {
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(A, start, mid); // 전반부 정렬
			mergeSort(A, mid + 1, end); // 후반부 정렬
			merge(A, start, mid, end);
		}
	}

	public static void merge(int[] A, int start, int mid, int end) {
		int part1 = start;
		int part2 = mid + 1;
		int index = 0;
		System.out.print("현재 배열 "+start +" 부터 "+end+" 까지: ");
		for(int i=start;i<=end;i++) {
			System.out.print(A[i]+ " ");
		}
		System.out.print("\n");
		
		
		while (part1 <= mid && part2 <= end) {
			if (A[part1] <= A[part2]) {
				System.out.println("PART1이 더 작음! 현재 index: "+index+ " 바꿀 자리: "+part1+", "+A[part1]);
				tmp[index++] = A[part1++];
			} else {
				System.out.println("PART2가 더 작음! 현재 index: "+index+ " 바꿀 자리: "+part2+", "+A[part2]);
				tmp[index++] = A[part2++];
			}
		}
		while (part1 <= mid) { // 왼쪽 배열 부분이 남은 경우
			System.out.println("왼쪽 배열 남음! 현재 index: "+index+ " 남은 자리: "+part1+", "+A[part1]);
			tmp[index++] = A[part1++];
		}
		while (part2 <= end) { // 오른쪽 배열 부분이 남은 경우
			System.out.println("오른쪽 배열 남음! 현재 index: "+index+ " 남은 자리: "+part2+", "+A[part2]);
			tmp[index++] = A[part2++];
		}
		part1 = start;
		index = 0;
		while (part1 <= end) { // 결과를 A[]에 저장
			A[part1++] = tmp[index++];
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st= new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		
		int[] A=new int[N];
		tmp= new int[A.length];
		st= new StringTokenizer(br.readLine());
		for(int i=0;i<A.length;i++) {
			A[i]=Integer.parseInt(st.nextToken());
		}
		
		mergeSort(A,0,A.length-1);
		for(int i=0;i<A.length;i++) {
			System.out.print(A[i]+ " ");
		}
	}
}

말은 참 쉬운데 코드 이해는 어렵다.

백준 24060번: 알고리즘 수업 - 병합 정렬 1

https://www.acmicpc.net/problem/24060

시간초과가 났는데 tmp[] 배열 정의를 main함수 쪽으로 옮겨주니 성공하였다.
이유를 모르겠다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	static int count=0;
	static int[] tmp;
	static int K;
	static StringTokenizer st;
	public static void merge_sort(int[] A,int p,int r) {
		
		if(p<r) {
			int q= (p+r)/2; 
			merge_sort(A,p,q);
			merge_sort(A,q+1,r);
			merge(A, p,q,r);
		}
	}

	public static void merge(int[] A,int p,int q,int r) {
	
		int i=p; 
		int j=q+1;
		int t=0;
		while(i<=q && j<=r) {
			if(A[i]<=A[j]) {
				tmp[t++] = A[i++];
			}else {
				tmp[t++]=A[j++];
			}
		}
		while(i<=q) {
			tmp[t++]=A[i++];
		}
		while(j<=r) {
			tmp[t++]=A[j++];
		}
		i=p;t=0;
		while(i<=r) {
			A[i++]=tmp[t++];
			count++;
			if(count==K) {
				System.out.println(A[i-1]);
				break;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st= new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		K= Integer.parseInt(st.nextToken());
		int[] A=new int[N];
		tmp= new int[A.length];
		st= new StringTokenizer(br.readLine());
		for(int i=0;i<A.length;i++) {
			A[i]=Integer.parseInt(st.nextToken());
		}
		merge_sort(A,0,A.length-1);
		
		if(count<K) {
			System.out.println(-1);
		}
	}
}	

병합정렬을 꽤 오랜기간 공부했는데 외워지질 않는다..

백준 24061번: 알고리즘 수업 - 병합 정렬 2

https://www.acmicpc.net/problem/24061
24061번 문제에서 출력만 다르게 하면 된다.
또 시간초과가 나서 이번에는
StringBuilder를 이용해 결과를 저장하고 버퍼에 StringBuidler를 넣어주는 방식으로 출력 시간을 줄여주었더니 성공하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int[] tmp;
	static StringTokenizer st;
	static int K;
	static StringBuilder str = new StringBuilder(); 
	static int count =0;
	public static void mergeSort(int[] A, int start, int end) {
		if(start<end) {
			int mid = (start+end)/2;
			mergeSort(A,start,mid);
			mergeSort(A,mid+1,end);
			merge(A,start,mid,end);	
		}
	}
	public static void merge(int[] A, int start,int mid,int end) {
		int part1= start;
		int part2= mid+1;
		int index=0;
		
		while(part1<=mid && part2<=end) {
			if(A[part1]<=A[part2]) {
				tmp[index++] = A[part1++];
			}else {
				tmp[index++] = A[part2++];
			}
		}
		while(part1<=mid) {
			tmp[index++]= A[part1++];
		}
		while(part2<=end) {
			tmp[index++]= A[part2++];
		}
		
		part1= start; index=0;
		
		while(part1<=end) {
			A[part1++] = tmp[index++];
			count++;
			if(count==K) {
				for(int i=0;i<A.length;i++) {
					str.append(String.valueOf(A[i]+" "));
				}
				break;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st= new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		K= Integer.parseInt(st.nextToken());
		int[] A=new int[N];
		tmp= new int[N];	
		st= new StringTokenizer(br.readLine());
		for(int i=0;i<A.length;i++) {
			A[i]=Integer.parseInt(st.nextToken());
		}
		mergeSort(A,0,A.length-1);
		bw.write(str.toString());
		if(count<K) {
			bw.write(String.valueOf(-1));
		}
		bw.flush();
		bw.close();
		br.close();
	}
}