자료구조와 함께 배우는 알고리즘 입문 [자바편] : 중앙값 구하기

최소값, 최대값 로직은 이용해볼 일이 많은데 중앙값 로직은 처음 봐서 일단은 책을 보지 않고 직접 고민해보았다.

 

한 가지의 경우만 고려하려고 하지 않았고 최대한 많은 경우의 수를 떠올리려 노력했다.

지하철에서 고민한 흔적들...

 

1 ) 맨 처음에는 모든 수들의 평균값을 구해서 평균값과 가장 가까운 수를 구하면 중앙값이 되지 않을까 했는데 그렇지 않다는 것을 알게 되었다.

 

왜냐하면 예를 들어

1, 2, 100 3개의 숫자가 있다.

이들의 평균값을 구하면 34.33... 이라는 숫자가 나오고 34.33...은 가장 큰 100이라는 숫자에 가깝기 때문에 절대 중앙값이 될 수 없다.

 

즉, 평균은 중앙값이 될 수 없다.

 

2 ) 그러다가 생각한 점은, 앞에서 최댓값 알고리즘을 작성할 때 모든 경우의 수를 일일이 if문으로 검사하였는데, 

중앙값도 if문으로 일일이 비교해서 찾으면 되지 않을까 하는 생각이었다.

a와 b를 비교해서 a가 클 때, 다시 c랑 a를 비교해서 c가 크면 a가 중앙값이고, a가 더 크면 c가 중앙값이 되는 것이다.

이 로직은 모든 정수들의 크기를 비교하므로 중앙값을 구할 수 있다고 생각하였다.

 

물론 3개의 수가 모두 같을 경우도 있을테니 이를 고려하여, a와 b, b와 c, c와 a를 비교할 때 처음에는 >=를 이용하여 값이 같을 경우도 고려하기로 했다.

 

[한글 코딩]

package class01;

public class Median {

	public static void main(String[] args) {
		
		중앙값은 + 중앙값 메소드(A,B,C) + 입니다. 출력
	}
	
	정수 반환형 중앙값 메소드(A, B, C) {
		
		스캐너 변수 선언

		정수 3개를 입력해주세요! 출력
		정수 A = 정수로 입력받음
		정수 B = 정수로 입력받음
		정수 C = 정수로 입력받음
		
		만약 (A가 B보다 같거나 크다면) { // A >= B
			만약 (B가 C보다 같거나 크다면) { // B > C 
				B를 반환 } // C < B < A  
			아니라면 {
				C를 반환 // B < C < A
				}
			만약(A가 C보다 작거나 같으면) { // B < A < C
				A를 출력
			}
		}
		
		만약 (A가 B보다 같거나 크지 않다면) { // A < B
			만약 (B보다 C가 크다면) { // B < C
				B를 반환 // A < B < C
			} 아니라면 {
				C를 반환 // A < C < B
			}
		
		만약 (C보다 A가 크다면 ) {   
			A를 반환 // C < A < B
		}
	}
}


	A B C - 3
	A C B - 4
	B A C
	B C A - 2
	C A B - 5
	C B A - 1

	6개의 경우의 수

한 정수가 중간에 올 수 있는 경우의 수를 먼저 생각한 후 한글 코딩을 천천히 작성했다. 6가지의 경우가 모두 나오도록!

 

[코드 작성]

	if (a >= b) {
			if (b >= c) {
				return b;
			} else if (a <= c) {
				return a;
			} else {
				return c;
			}
		} else {
			if (b <= c) {
				return b;
			} else if (a > c) {
				return a;
			} else {
				return c;
			}
		}
	}
}

한글코딩을 바탕으로 코드를 짜고 나니까 어딘가 이상함을 느낌..

한글코딩 잘못 썼다 ㅠ

 

메인문에는 리턴값 불가!!

 

배열에 들어있는 값 중 중앙값 구하기

package class01;

import java.util.Random;
import java.util.Scanner;

public class ArrayMedian {

	/*	
		배열 속 중앙값 구하기
		배열 길이는 사용자에게 받기
		배열의 값은 랜덤으로 받아온다
	 * 
	 * */

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in); // 	스캐너 객체 생성
		Random rand = new Random(); //	랜덤 객체 생성

		int len; // 배열의 길이를 저장할 변수 선언

		while(true) {// 무한루프 

			System.out.println("배열의 길이를 입력해주세요 ! (3-10 사이)"); // 배열의 길이를 입력해주세요 ! 출력 (3-10 제한)
			len = sc.nextInt(); // 사용자가 정수로 입력


			if(len >= 3 && len <= 10) { // 만약(올바른 수를 입력하면)
				break; //	"탈출"
			}
		}

		int[] numList = new int[len]; // 정수형 배열 선언 = {배열 길이 저장 변수}

		for(int i = 0; i < len; i++) {
			numList[i] = rand.nextInt(101); // 배열 = 랜덤.정수형입력 100까지의 랜덤 수 // 랜덤값 집어넣기
		}

		System.out.print("정렬 전 배열 : [");
		for (int i = 0; i < numList.length; i++) {
			System.out.print(numList[i] + " ");
		} // i + " "로 인덱스번호만 출력중이었네;;
		System.out.println("]"); 


		selectionSort(numList, len); // // 오름차순 로직. 선택정렬 사용

		double median;

		// 중앙값 찾기 로직. 홀수/짝수
		if(numList.length % 2 == 1) { // 	만약 (배열의 길이가 홀수라면) {
			median = numList[numList.length / 2];  // 배열 길이 / 2한 인덱스 번호 값을 가져온다
		} else { //  (배열의 길이가 짝수라면) 
			median = (numList[numList.length / 2 - 1] + numList[numList.length / 2]) / 2.0;  // ((배열 길이 /2) -1 ) + (배열 길이 / 2) / 2.0

		}

		// 현재 배열 출럭 
		System.out.print("정렬된 배열: [");
		for (int i = 0; i < numList.length; i++) {
			System.out.print(numList[i] + " ");
		}
		System.out.println("]");
		
		System.out.println("중앙값은" + median + "입니다.");

	}

	private static void selectionSort(int[] numList, int len) {

		for(int i = 0; i < len - 1; i++) {
			int minIndex = i;	
			for(int j = i + 1; j < len; j++) {
				if(numList[j] < numList[minIndex]) {
					minIndex = j;
				}
			}
			swap(numList, minIndex, i);
		}
	}

	private static void swap(int[] numList, int i, int j) {
		int temp = numList[i];
		numList[i] = numList[j];
		numList[j] = temp;
	}
}