오늘부터 자료구조와 함께 배우는 알고리즘 책을 공부하기 시작했다.

최대 값을 구하는 알고리즘은 max라는 가장 첫 값에 대입하고, 나머지 값들과 대소비교를 하는 방식으로 차례대로 대입하여 쉽게 구할 수 있었던 반면에, 중간 값은 많이 복잡한 방식을 취하고 있고, 이해하기가 어려웠다.

책을 보고 바로 이해가 되지 않아서 직접 코딩하고 경우의 수를 세가면서 해보니 이해가 갔다.

1. a가 b보다 크거나 같으면서, b가 c보다 크거나 같을 때

if(a>=b) {
	if(b>=c) {
		med = b;

If문을 중첩해서 a가 b보다 크거나 같으면서, b가 c보다 크거나 같을때는 중간 값이 b가 된다.

2. a가 b보다 크거나 같으면서, c가 a보다 작거나 같을때

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

a가 b보다 크거나 같고, c가 a보다 작거나 같게 되면
중간 값은 c가 되게 된다.

3. a가 b보다 크거나 같고, c가 b보다 크거나 같을때

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

a가 b보다 크거나 같고, c가 b보다 크거나 같은 조건은
else문으로 처리했다. 위의 If문과 else if문에서 조건에 부합한 것은 처리 하기 때문에, 그 외의 조건만 med(중간값)의 값으로 a를 취하면 되므로, 이렇게 처리했다.

4. a가 b보다 작고, a가 c보다 클때

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

a와 b를 비교해서 a가 b보다 크거나 같으면 중첩 If문 속에 있는 조건들을 비교하는데, a가 b보다 작은 경우에는 바깥쪽 else if문에서 조건들을 비교하여 med의 값을 정한다.

a가 b보다 작고, a가 c보다 크다면 a < b && a > c 이다
그렇다면 a가 b보다 작은데 a보다 작은 c가 b보다는 크거나 같을리 없으므로 , a가 중간 값이 된다.

5. a가 b보다 작고, b가 c보다 클때

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

a가 b보다 작고, b가 c보다 크다면, a<b && b>c 일것이다.
그렇다면 a가 b보다 작고, b가 c보다 크다는 것일텐데,
여기서 반례를 생각해 본것이, a가 b보다 작고 b가 c보다 크면서 a보다 c가 크면 어떻게 될까 하는 생각이였는데
판단 미스였다 왜냐하면 여기서 a와 c의 대소비교가 빠졌다는 생각을 했기 때문이다.
a가 b보다 작고, b가 c보다 크면서 a가 c보다 크다면,
그 조건은 이미 위의 else if문에서 a>c 조건에 걸려서 처리되기 때문에 그것은 고려할 필요가 없는 문제였다.
따라서 중앙값은 c가 된다.

6. a가 b보다 작고, c가 b보다 큰 경우

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

a가 b보다 작고 c가 b보다 크다면 예를 들면
4,5,8 과 같은 경우일 것이다. 4가 5보다 작고, 8이 5보다 큰 수 이므로, 5가 중간 값이된다.
세 개의 수에서 중간 값이란 중복되는 값이 없을 경우,
어떤 수보다는 크고, 어떤 수보다는 작은 값이 되어야 하기 때문이다.

전체 코드

Scanner로 3개의 정수 a,b,c 를 입력받고 중간 값을 출력하는 프로그램을 작성해 보았다. 책에 포함되어 있는 결정트리(모든 경우의 수)를 확인하여 13가지의 모든 경우의 수를 확인 한 결과 제대로 출력 되는 것을 확인하였다.

import java.util.Scanner;
public class Med3 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int med = 0;
		int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt();
if(a>=b) {
	if(b>=c) {
		med = b;
	}else if(c<=a) {
		med = c;
	}else {
		med = a;
	}	
}else if(a>c) {
	med = a;
}else if(b>c) {
	med = c;
}else {
	med = b;
}
System.out.println("중간값 : " + med);
	}
}