순서대로 입력되는 시간 값을 보고 언제 가장 많이 겹치는지 계산하는 문제 1초 간격으로 계산하기 때문에 처음 입력 시간을 받을 때, 처음 비교 시간 -1초, 나중 비교 시간 +1초를 해주고, count 해주었습니다. 배열의 크기는 트래픽 도착 시간이 순차적으로 들어오기 때문에 (가장 나중에 들어온 시간 + 1) - (가장 먼저 들어온 시간 - T의 최댓값 - 1)으로 계산했습니다. ex) lines = { "2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s" } 일 때, "2016-09-15 01:00:04.001 2.0s"는 2016-09-15 01:00:04.001 - 2.0s - 1s = 2016-09-15 01:00:01.002부터 2016-..

QuickSort는 주어진 array를 분할 정복하고, pivot을 설정해 pivot과 비교하며 정렬하는 방법입니다. pivot 설정은 개발자에 따라 다르게 설정할 수 있지만, 보통은 중앙값을 pivot으로 설정합니다. 분할 정복을 하기 때문에 최소, 평균 시간복잡도가 O(n*log n)이지만, pivot과 비교되는 값이 항상 조건에 충족되어 pivot을 지속해서 바꿔주어야 하는 경우(최악의 경우) O(n^2)이 됩니다. 기존의 array에서 값을 변경하기 때문에 공간복잡도는 1입니다. 자바와 벡터를 이용해 QuickSort를 구현해 보겠습니다. Java 코드 import java.util.Vector; public class QuickSort { static void quickSort(Vector v,..

합병 정렬은 주어진 array를 지속적으로 쪼개어 최소 array에서 값을 비교해 다시 합치고 정렬하는 방식으로 최소, 최대, 평균 시간 복잡도가 O(n*log n)으로 비교적 가장 빠른 정렬 방법입니다. 쪼개진 array를 정렬하여 저장하기 위한 별도의 copy array가 필요하기 때문에 공간복잡도는 n입니다. 자바와 벡터를 이용해 합병 정렬을 구현해 보겠습니다. Java 코드 package sort; import java.util.Vector; public class MergeSort { static void merge(Vector v, int s, int e, int m) { Vector ret = new Vector(); int i = s; int j = m + 1; while (i