[Algorithm] Chapter01 연습문제 Q4 ~ Q5 p22

Q4 세 값의 대소 관계 13종류의 모든 조합에 대해 중앙값을 구하여 출력하는 프로그램을 작성하세요.

 

내 답안

import java.util.Arrays;
import java.util.Random;

public class chap_01_q4_med3 {
    public static void main(String[] args) {
        int arr[] = new int[7];
        int repeat = 1;
        for(int i = 0; i < arr.length; i++){
            if(i != 0 && i % (arr.length-1) == 0) {
                System.out.println("배열은 " + Arrays.toString(arr) + "이며");
                System.out.println("중간 값은 " + med(arr) + "입니다.\n");

                if(++repeat > 5) i = arr.length;
                else i = 0;
            }
            else{
                arr[i] = new Random().nextInt(9)+1;
            }
        }
    }

    private static int med(int [] arr) {

        int index = 0;
        int min = arr[0];
        int max = arr[0];
        int med = arr[0];

        while(index<arr.length -1){
            index++;
            if(min > arr[index]) {
                min = arr[index];
                index = 0;
            }
            if(max < arr[index]) {
                max = arr[index];
                index = 0;
            }

            int medValue = 0;
            if((max + min) % 2 == 0) medValue = (max + min) / 2;
            else medValue = (max + min) / 2 + 1;

            if(abs(medValue - arr[index]) < abs(medValue - med)) med = arr[index];

        }

        return med;
    }

    private static int abs(int a){
        if(a < 0) return -a;
        else return a;
    }
}

 

결과 값

배열은 [3, 2, 4, 5, 4, 6, 0]이며
중간 값은 3입니다.

배열은 [3, 2, 4, 8, 5, 2, 0]이며
중간 값은 4입니다.

배열은 [3, 1, 1, 8, 7, 6, 0]이며
중간 값은 3입니다.

배열은 [3, 3, 7, 4, 3, 1, 0]이며
중간 값은 4입니다.

배열은 [3, 4, 6, 6, 9, 3, 0]이며
중간 값은 6입니다.

 

해당 답안

package chap01;
// 세 정수값의 중앙값을 구하여 나타냄 (모든 조합의 대소관계에 대하여 검증)

class Med3_01_04 {
	// a, b, c의 중앙값을 구하여 반환
	static int med3(int a, int b, int c) {
		if (a >= b)
			if (b >= c)
				return b;
			else if (a <= c)
				return a;
			else
				return c;
		else if (a > c)
			return a;
		else if (b > c)
			return c;
		else
			return b;
	}

	public static void main(String[] args) {
		System.out.println("med3(3,2,1) = " + med3(3, 2, 1)); // a＞b＞c
		System.out.println("med3(3,2,2) = " + med3(3, 2, 2)); // a＞b＝c
		System.out.println("med3(3,1,2) = " + med3(3, 1, 2)); // a＞c＞b
		System.out.println("med3(3,2,3) = " + med3(3, 2, 3)); // a＝c＞b
		System.out.println("med3(2,1,3) = " + med3(2, 1, 3)); // c＞a＞b
		System.out.println("med3(3,3,2) = " + med3(3, 3, 2)); // a＝b＞c
		System.out.println("med3(3,3,3) = " + med3(3, 3, 3)); // a＝b＝c
		System.out.println("med3(2,2,3) = " + med3(2, 2, 3)); // c＞a＝b
		System.out.println("med3(2,3,1) = " + med3(2, 3, 1)); // b＞a＞c
		System.out.println("med3(2,3,2) = " + med3(2, 3, 2)); // b＞a＝c
		System.out.println("med3(1,3,2) = " + med3(1, 3, 2)); // b＞c＞a
		System.out.println("med3(2,3,3) = " + med3(2, 3, 3)); // b＝c＞a
		System.out.println("med3(1,2,3) = " + med3(1, 2, 3)); // c＞b＞a
	}
}

문제에서는 3개의 숫자를 갖고 만든 모든 조합에 대해 중앙값을 구하는 메서드를 구현하라고 했지만 그냥 구현한 김에 숫자의 배열에서 중간 값을 구하는 메서드를 구현해 보았다. 

 

 

Q5 중앙값을 구하는 메서드는 다음과 같이 작성할 수도 있습니다. 그러나 실습 1C-1의 med3 메서드에 비해 효율이 떨어지는데, 그 이유를 설명하세요.

static int med3(int a, int b, int c){
    if((b >= a && c <= a) || (b <= a && c >= a))
        return a;
    else if((a > b && c < b) || (a < b && c > b))
        return b;
    return c;
}

 

내 답안

if 문의 앞 조건 각 각 (b >= a && c <= a), (a > b && c < b)가 true면 || (or) 이기 때문에 바로 retrun으로 넘어가 괜찮지만 false가 나오게 되면 뒤에 나오는 조건도 확인해야 해서 가장 적은 경우의 수가 두 번 그렇지 않으면 네 번으로 두 번 또는 네 번을 검사한다.

하지만 1C-1의 med3(Q4의 해당 답안과 같다.)의 경우 최소 두 번에서 최대 네 번까지로 이 메서드에서 세 번 검사하는 경우는 예시에서 제시하는 메서드는 네 번 검사해야 하기 때문에 효율이 떨어진다.

 

<요약>

1C-1 메서드의 경우 2 ~ 4 번까지 검사하는 경우의 수가 있고 세 번 검사하는 경우 예시로 제공하는 메서드에서는 네 번 검사해야 해서 효율이 떨어진다.

 

Q5는 해당답안이 따로 없다.