[BaekJoon] 11004 K번째 수 (java)

🔗 문제 링크

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

👨🏻‍💻 Arrays.sort를 사용한 코드 (통과)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int numberOfArray = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[numberOfArray];
		
		st = new StringTokenizer(br.readLine());
		for (int i=0; i < numberOfArray; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		System.out.println(arr[k-1]);

		
	}

}

👨🏻‍💻 Merge sort를 사용한 코드 (시간 초과)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int numberOfArray = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		List<Integer> list = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine());
		for (int i=0; i < numberOfArray; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		list = split(list);

		System.out.println(list.get(k-1));

		
	}
	
	// Recursive하게 List를 절반으로 나눠주고 다시 병합해준다.
	public static List<Integer> split(List<Integer> list){
		if (list.size() <= 1)
			return list;
		
		int listSize = list.size();
		List<Integer> left = list.subList(0, listSize/2);
		List<Integer> right = list.subList(listSize/2, listSize);
			
		left = split(left);
		right = split(right);
		return merge(left, right);
	}
	
	
	
	// 2개의 list를 앞의 수를 계속 비교해가며 작은 수부터 merged list에 넣어 정렬하며 합친다.
	public static List<Integer> merge(List<Integer> left, List<Integer> right){
		// left, right가 둘 다 있을 때
		int leftPoint = 0;
		int rightPoint = 0;
		List<Integer> merged = new ArrayList<>();
		while(left.size() > leftPoint && right.size() > rightPoint) {
			if(left.get(leftPoint) < right.get(rightPoint)) {
				merged.add(left.get(leftPoint));
				leftPoint++;
			}
			else {
				merged.add(right.get(rightPoint));
				rightPoint++;
			}
		}
		
		// left가 없을 때
		while (left.size() > leftPoint) {
			merged.add(left.get(leftPoint));
			leftPoint++;
		}
		
		// right가 없을 때
		while (right.size() > rightPoint) {
			merged.add(right.get(rightPoint));
			rightPoint++;
		}
		
		return merged;
	}

}

📝 정리

이번에도 처음 문제를 풀고 성능 향상을 위해 코드를 다시 작성해보았다.

Arrays.sort의 경우 기본적으로 Dual Pivot Quick Sort 알고리즘으로 sort하고 시간 복잡도는 $O(nlogn)$을 기대할 수 있지만, 최악의 경우 $O(n^2)$가 나올 수 있어서 $O(nlogn)$의 시간복잡도를 갖는 merge sort를 구현하여 실행시켜보았다.

일단 실행 결과는 시간 초과라는 결과가나왔다. 아무래도 배열이 아닌 List를 사용하였고 함수를 계속 호출하며 list를 쪼개고 합치는 연산을 계속 하여 시간적으로 많이 걸려서 시간초과라는 결과가 나온 것 같다.