버블정렬 이중for문 로직 + 중앙값 구하기

사실 sort() 쓰면 된다

 

class Solution {
    public int solution(int[] array) {
        int answer = 0;
        for(int i=0; i<array.length-1; i++) {
            for(int j=i; j<array.length-1; j++) {
                if(array[i] > array[j+1]) {
                    int temp = array[j+1];
                    array[j+1] = array[i];
                    array[i] = temp;
                }
            }
        }
        answer = array[array.length/2];
        return answer;
    }
}

 

---

중앙값 구하기

배열에 숫자를 넣고 그 중간값을 출력해주는 형태로 짜면 된다

 

중앙값은 일반적으로 배열의 길이가 홀수, 그리고 나열된 숫자들이 홀수개일 때 구하는 값이다

 

숫자로 따져봤을때, 배열의 길이가 3이라면 중앙값은 1 2 3 에서 2번째에 있는 값이 중앙값이다

그렇다면, 이걸 수학적으로 생각해봤을 때

		/**
		 * 3의 중앙값 2 2 = 3 - 1 << 1이 몫, 나머지 1
		 * 5의 중앙값 3 3 = 5 - 2 << 2가 몫, 나머지 1
		 * 7의 중앙값 4 4 = 7 - 3 << 3이 몫, 나머지 1
		 * 9의 중앙값 5 5 = 9 - 4 << 4가 몫, 나머지 1
		 * 11의 중앙값 6 6 = 11 - 5 << 5가 몫, 나머지 1
		 * 
		 * 공통점 : 2로 나눔
		 */

 

대충 이런식으로 생각해볼 수 있다

 

5의 중앙값은 3이다. 1 2 3 4 5 에서 중간에 있는 값이 3이기 때문

그럼 이걸 수학적으로 표현해봤을 때, 중간값인 3을 구하려면 주어진 숫자를 활용했을 때, 3 = 5 - 2 가 된다

 

그럼 항등식에 의해 5 = 3 + 2 라는 값이 도출되고

이는 5 = 3*1 + 2 가 되어 일종의 유클리드 호제법과 비슷해진다

 

마찬가지로 11의 중앙값은 세어보면 6이고, 이는 6 = 11 - 5 - > 11 = 6 + 5이다.

 

생각해보면 5와 3은 나누어 떨어지는게 1과 자기 자신뿐인 값이므로 나머지가 반드시 1이 나오게 된다

또한 홀수의 특징에 의해 2라는 값으로 나누면 반드시 나머지가 1이 나오게 된다

 

헛소리를 크게 적었는데, 결국 배열의 총 길이를 2로 나눈 몫을 구하면 된다.

 

따라서 아래와 같은 형태로 중앙값을 나타내볼 수 있다

array.length/2

 

 

 

하지만 array.length/2를 통해 홀수를 나누게 되면 어떤 값이 나오게 되는가에 대한 의문이 생길 수 있다.

 

5를 2로 나누면 몫이 2고, 나머지가 1이 되지 않는가?

 

이건 배열이 0부터 시작한다는것을 생각해보면 이해가 쏙쏙 된다!

만약 배열이 1부터 시작한다면

array.length/2 + 1

 

이렇게 해줘야한다. array[1], array[2], ... array[5] 이렇게 될테니까

 

하지만 배열은 0부터 시작하고 배열의 길이가 5라면 0 ~ 4일테니 array.length/2를 통해 몫을 구하여 중앙값을 찾는게 좋다

 

 

---

버블 정렬

말했지만, array를 사용하기 때문에 그냥 sort() 메서드 써주면 된다

 

하지만, 버블정렬에 대한건 알지만 sort() 메서드를 몰랐던 나같은 어린 양들은 이중for문을 생각할 것이다

		for(int i=0; i<array.length; i++) { // i = 0
			for(int j = i; j<array.length; j++) {
				if(array[i] > array[j]) {
					int temp = array[j];
					array[j] = array[i];
					array[i] = temp;
				}
			}
		}

 

이런식으로 완성해봤다.

 

핵심은

1. for문이 반드시 2개 있어야한다.

		/**
		 * array.length = 7
		 * i가 0일때 j 반복문의 array.length = 7-1 = 6 0부터 6까지
		 * i가 1일때 j 반복문의 array.length = 7-1 = 5 1부터 6까지
		 * i가 2일때 j 반복문의 array.length = 7-1 = 4 2부터 6까지
		 */

 

for문이 1개밖에 존재하지 않는다면 '첫번째' 값에 대해서만 정렬을 진행하고 나머지 값들은 정렬이 진행되지 않는다.

따라서 배열 첫번째 값의 정렬을 진행하고, 두번째 값의 정렬 또한 진행해줘야 하기 때문에

이러한 로직을 for문 안에 다른 for문을 넣어줌으로 짜주면 된다

 

 

2. array[i]와 array[j]를 비교해야함

array[i]와 array[i+1]을 비교하면 안된다

 

어.. 돌려보면 안다

 

 

 

다시 말하지만, 이 뻘짓을 하지 않고

array.sort()

 

를 쓰면 내부적으로 정렬이 된다