[JAVA] 백준 2108번 통계학 : 정렬

2108번: 통계학

 

1. 문제 추상화

 

주어진 수들의 산술평균, 중앙값, 최빈값, 범위를 구하시오.

 

2. 알고리즘

 

1) 정렬 알고리즘

 

퀵정렬, 합병정렬, 카운팅 정렬, 힙정렬로 풀어볼 것이다. ( 참고로 버블정렬은 시간초과가 난다. )

 

(각 정렬의 알고리즘은 아래 포스팅을 참고바랍니다!)

[알고리즘] 퀵 정렬 (Quick Sort)

[알고리즘] 합병 정렬 ( Merge Sort )

[알고리즘] 힙 정렬 ( Heap Sort )

[JAVA] 백준 10989번 수 정렬하기 3 : 카운팅 정렬 (Counting Sort)

 

 

2) 최빈값 알고리즘 

 

산술평균, 중앙값, 최빈값, 범위 중에 가장 어려운 최빈값 알고리즘만 살펴보겠다. 최빈값이란 중복이 가장 많이 된 수를 의미한다. 여기에 귀찮은 조건 하나가 있다. 동일한 최대 중복횟수를 가진 수가 2개 이상 있다면 두 번째로 작은 수가 최빈값이 된다. 

 

-1 -1 0 1 1 1 2 5 5 5 13 13 

 

예를 들어, 위 수의 나열에서 중복이 가장 많이 된 수는 1과 5이다. 1은 첫 번째로 작고 5가 두 번째로 작다. 고로 최빈값은 5가 된다. 

 

 

▶ 풀이 순서 

 

 

1. 카운팅 2차원 배열 생성

정렬 알고리즘을 통해, 오름차순으로 정렬하였다. 그리고 카운팅 2차원 배열을 만든다. 카운팅 2차원 배열은 2개의 방을 중복을 배제한 수의 나열만큼 만든다.

 

 

2. 최빈값 탐색

카운팅 2차원 배열이 완성되면 최빈값을 탐색할 차례이다. 중복이 가장 많이 된 수 중 두 번째로 작은 수를 구하기 위해 플래그 변수를 사용한다.

 

 

 

반복문을 사용하여 배열을 선형탐색한다. 중복횟수가 가장 많은 값을 탐색하면서 플래그 변수가 FALSE -> TRUE로 바뀌는 위치의 값을 최빈값으로 저장한다. 

 

 

3. 코드

 

< 최빈값 코드 >

 

	//최빈값
	public static int getMaxFrequencyValue() {
		int[][] valueCountArr = new int[arr.length][2]; // 카운팅 2차원 배열 생성
		int valueCountPointer = initializeValueCountArr(valueCountArr); // 카운팅 2차원 배열 초기화
		return getMaxFrequencyValue(valueCountArr, valueCountPointer); // 최빈값 탐색
	}
    
        // 카운팅 2차원 배열 초기화
        public static int initializeValueCountArr(int[][] valueCountArr) {
          int valueCountPointer = -1;
          int beforeValue = MAX + 1; // MAX = 4000

          for(int value : arr) {
              if( beforeValue == value ) { // 이전 값과 중복되면 카운팅을 1 증가시킨다.
                  valueCountArr[valueCountPointer][1]++;
              }else {  // 이전 값과 중복 안 되면 배열에 저장하고 카운팅을 1 증가시킨다.
                  valueCountPointer++;
                  valueCountArr[valueCountPointer][0] = value;
                  valueCountArr[valueCountPointer][1]++;
                  beforeValue = value;
              }
          }
          return valueCountPointer; // 카운팅 배열 크기 반환
          }

       //최빈값 탐색
       public static int getMaxFrequencyValue(int[][] valueCountArr, int valueCountPointer) {
          boolean second = false; // 플래그 변수
          int duplicateMax = 0; // 최대 중복횟수
          int maxFrequencyValue = 0; // 최빈값

          // 탐색시작
          for(int i = 0; i <= valueCountPointer; i++) {
              if( valueCountArr[i][1] > duplicateMax ) { // 최대중복횟수인 경우
                  duplicateMax = valueCountArr[i][1];// 최대중복횟수 저장
                  maxFrequencyValue = valueCountArr[i][0]; // 최빈값 저장
                  second = false; // 첫 번째이므로 false 저장
              }else if(valueCountArr[i][1] == duplicateMax ) {
                  if(!second) { // 최대중복횟수와 같은데 second 플래그가 false라면?
                      maxFrequencyValue = valueCountArr[i][0]; // 최빈값 저장
                      second = true; // 두 번째이므로 true 저장
                  }
              }
          }

          return maxFrequencyValue; // 최빈값 반환
      }

 

 

< 퀵정렬 코드 >

 

	// 퀵정렬 시작
	public static void doQuickSort(int left, int right) {
		
		int leftPointer = left;
		int rightPointer = right;
		int center = (left + right)/2;
		int pivot = arr[center];
		
		while(leftPointer <= rightPointer) {
			while(arr[leftPointer] < pivot ) leftPointer++;
			while(arr[rightPointer] > pivot ) rightPointer--;
			
			if(leftPointer <= rightPointer) swap(leftPointer++, rightPointer--);
		}
		
		if(left < rightPointer) doQuickSort(left,rightPointer);
		if(leftPointer < right) doQuickSort(leftPointer,right);
		
	}
	
	public static void swap(int leftPointer, int rightPointer) {
		int tmp = arr[leftPointer];
		arr[leftPointer] = arr[rightPointer];
		arr[rightPointer] = tmp;
	}

 

 

< 합병 정렬 코드 >

 

	// 병합정렬 시작
	public static void doMergeSort(int left, int right) {
		if(left < right) {
			int center = ( left + right )/2;
			
			doMergeSort(left,center);
			doMergeSort(center+1,right);
			
			applyMerge(left, right);
		}
	}
    
	// 병합 알고리즘
	public static void applyMerge(int left, int right) {
		int[] leftArr = new int[right - left + 1];
		int leftSize = 0;
		int center = ( right + left )/2;
		int leftPointer = 0;
		int rightPointer = center+1;
		int arrPointer = left;
		
		for(int i = left; i<=center; i++) {
			leftArr[leftSize++] = arr[i];
		}
		
		for(arrPointer = left; arrPointer <= right; arrPointer++) {
			if( leftPointer < leftSize && rightPointer <= right ) {
				arr[arrPointer] = leftArr[leftPointer] < arr[rightPointer] ? leftArr[leftPointer++] : arr[rightPointer++];
			}else {
				break;
			}
		}
		
		while(leftPointer < leftSize) {
			arr[arrPointer++] = leftArr[leftPointer++];
		}
	}

 

 

< 힙 정렬 코드 >

 

	// 힙정렬 시작
	public static void doHeapSort() {
		int lastChildIndex= arr.length - 1;
		int lastParentIndex= ( lastChildIndex - 1) / 2;
		
		for(int i = lastParentIndex; i >= 0; i--) {
			makeHeap(i,lastChildIndex);
		}
		
		for(lastChildIndex=arr.length-1; lastChildIndex > 0;lastChildIndex--) {
			swap(lastChildIndex);
			makeHeap(0,lastChildIndex-1);
		}
	}
	
	// 힙정렬 알고리즘
	public static void makeHeap(int startParentIndex, int lastChildIndex) {
		
		int pivot = arr[startParentIndex];		
		int heapPointer = 0;
		int childIndex= 0;

		for(heapPointer = startParentIndex; heapPointer<(lastChildIndex + 1)/2; heapPointer = childIndex) {
			
			int leftChildIndex = heapPointer*2 + 1;
			int rightChildIndex = leftChildIndex +1;
			
			if(rightChildIndex > lastChildIndex) childIndex = leftChildIndex;
			else childIndex = arr[leftChildIndex] > arr[rightChildIndex] ? leftChildIndex : rightChildIndex;
			
			if( pivot >= arr[childIndex]) break;
			else {
				arr[heapPointer] = arr[childIndex];
			}
		}
		arr[heapPointer] = pivot;
	}

 

 

<카운팅 정렬 코드>

 

	// 카운팅 시작
	public static void doCountingSort() {
		int countingMax = getMaxValue();
		int[] countingArr = new int[countingMax*2+1];
		
		for( int value : arr) {
			countingArr[value+countingMax]++;
		}
		
		int arrPointer = 0;
		for( int i = 0; i< countingArr.length; i++ ) {
			for( int j = 0; j < countingArr[i]; j++) {
				arr[arrPointer++] = i - countingMax;
			}
		}
	}

 

 

<전체 코드 ( 퀵정렬 기준 ) >

 

정렬 알고리즘 코드만 다르고 나머지 코드는 모두 동일하다.

 

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

//퀵정렬
public class Main {
	
	private static final int MAX = 4000;
	private static BufferedReader bufferedReader;
	private static BufferedWriter bufferedWriter;
	private static StringBuilder stringBuilder;
	
	private static int[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		createObjects();
		createArr();
		initializeArr();
		doQuickSort(0,arr.length-1);
		printResult();
		closeIO();
	}
	
	public static void createObjects() {
		bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
		stringBuilder = new StringBuilder();
	}
	
	public static void createArr() throws NumberFormatException, IOException {
		int size = Integer.parseInt(bufferedReader.readLine());
		arr = new int[size];
	}
	
	public static void initializeArr() throws NumberFormatException, IOException {
		for(int i=0; i< arr.length;i++) {
			arr[i] = Integer.parseInt(bufferedReader.readLine());
		}
	}
	
	// 퀵정렬 시작
	public static void doQuickSort(int left, int right) {
		
		int leftPointer = left;
		int rightPointer = right;
		int center = (left + right)/2;
		int pivot = arr[center];
		
		while(leftPointer <= rightPointer) {
			while(arr[leftPointer] < pivot ) leftPointer++;
			while(arr[rightPointer] > pivot ) rightPointer--;
			
			if(leftPointer <= rightPointer) swap(leftPointer++, rightPointer--);
		}
		
		if(left < rightPointer) doQuickSort(left,rightPointer);
		if(leftPointer < right) doQuickSort(leftPointer,right);
		
	}
	
	public static void swap(int leftPointer, int rightPointer) {
		int tmp = arr[leftPointer];
		arr[leftPointer] = arr[rightPointer];
		arr[rightPointer] = tmp;
	}

	
	// 결과 출력
	public static void printResult() throws IOException {
		stringBuilder.append(getAvg()).append("\n"); // 평균
		stringBuilder.append(getMedian()).append("\n"); // 중간값
		stringBuilder.append(getMaxFrequencyValue()).append("\n"); //최빈값
		stringBuilder.append(getRange()).append("\n"); // 범위
		
		bufferedWriter.write(stringBuilder.toString());
		bufferedWriter.flush();
	}
	
	// 평균
	public static int getAvg() {
		double sum = 0;
		for( int value : arr) {
			sum += value;
		}
		return (int)Math.round(sum/arr.length);
	}
	
	// 중간값
	public static int getMedian() {
		return arr[arr.length/2];
	}
	
	//최빈값
	public static int getMaxFrequencyValue() {
		int minValue = MAX+1;
		int maxValue = -MAX-1;
		int[] maxFrequencyArr = new int[2*MAX + 1];
		
		for( int value : arr ) {
			maxFrequencyArr[value+MAX]++;
			minValue = Math.min(minValue, value);
			maxValue = Math.max(maxValue, value);
		}
		
		boolean second = true;
		int maxFrequency = 0;
		int maxIndex = 0;
		
		for(int i = minValue + MAX; i <= maxValue + MAX; i++) {
			if(maxFrequencyArr[i] > maxFrequency) {
				maxFrequency = maxFrequencyArr[i];
				maxIndex = i;
				second = true;
			}else if(maxFrequencyArr[i] == maxFrequency) {
				if(second) {
					maxIndex = i;
					second = false;
				}
			}
		}
		
		return maxIndex - MAX;
	}
	
	// 범위
	public static int getRange() {
		return arr[arr.length-1] - arr[0];
	}
	
	public static int initializeValueCountArr(int[][] valueCountArr) {
		int valueCountPointer = -1;
		int beforeValue = MAX + 1;
		
		for(int value : arr) {
			if( beforeValue == value ) {
				valueCountArr[valueCountPointer][1]++;
			}else {
				valueCountPointer++;
				valueCountArr[valueCountPointer][0] = value;
				valueCountArr[valueCountPointer][1]++;
				beforeValue = value;
			}
		}
		
		return valueCountPointer;
	}
	
	public static int getMaxFrequencyValue(int[][] valueCountArr, int valueCountPointer) {
		boolean second = true;
		int max = 0;
		int maxFrequencyValue = 0;
		
		for(int i = 0; i <= valueCountPointer; i++) {
			if( valueCountArr[i][1] > max ) {
				max = valueCountArr[i][1];
				maxFrequencyValue = valueCountArr[i][0];
				second = true;
			}else if(valueCountArr[i][1] == max ) {
				if(second) {
					maxFrequencyValue = valueCountArr[i][0];
					second = false;
				}
			}
		}
		
		return maxFrequencyValue;
	}
	
	public static void closeIO() throws IOException {
		bufferedWriter.close();
		bufferedReader.close();
	}
}