[공부 필기] Java 기본 공부하기 (32)

공부 중인 강의 : 윤성우 선생님, 윤성우의 열혈 Java 프로그래밍 강의.

링크 : https://cafe.naver.com/cstudyjava

윤성우의 프로그래밍 스터디그룹 [C/... : 네이버 카페

 

※ 강의 청강 중 필요한 내용만 필기함

※ 틀린 필기가 있을 수 있음..

 

---

1. 배열의 탐색

- 배열의 정렬을 이해했다면 탐색은 엄청 쉽게 넘어갈 수 있음

   → 특히, compareTo 메소드를 잘 이해하면 좋음

 

- 특정 값을 찾을 때 탐색을 이용함

   → 특정 값이 있는지 없는지 찾을 때

   → 특정 값이 어느 위치에 있는지 찾을 때

- 그러다보니 일반적으로 탐색의 대상은 [배열]이 됨

 

- 탐색을 하기 위해 사용할 메소드는 binarySearch 메소드

   → 이 메소드의 탐색 대상은 [배열]임

   → binarySearch 메소드 또한 Arrays.sort 메소드처럼 오버로딩이 잘 되어 있음

[그림1]

   → binarySearch 메소드의 첫번째 인자는 "탐색 대상(어디에서 값을 찾을 것인지)"이고,

        두번째 인자는 "키 값(어떤 값을 찾을 것인지)"임

        * 만약 key 값(찾고자 하는 값)이 있다면 인덱스(찾고자 하는 값의 위치)를 반환하고 없으면 0보다 작은 수를 반환함

 

- binarySearch 메소드가 값(key)을 찾는 방법(알고리즘)은 [이진 탐색]임

   * 이진탐색은 일단 [탐색 대상]이 오름차순 정렬되어 있어야함

   * 탐색 방법을 간단하게 정리하면 아래와 같음

예시 : 10 20 30 40 50 55 60
찾고자 하는 값 : 55

   * 탐색 대상의 중간 값을 하나 찝어서 찾고자 하는 값(= key)과 비교해서 큰지, 작은지 체크

10 20 30 "40" 50 55 60

중간 값 "40"을 pick
찾고자 하는 값(55)과 중간 값(40)을 비교

   * 만약 중간 값이 key보다 작다면, key는 중간 값 기준으로 오른쪽에 있다는 이야기

50 55 60

찾고자 하는 값(55)은 중간 값(40)보다 크기 때문에 오른쪽에 있을 것

   * 남은 데이터들 중에서 다시 중간 값을 찾고, 그 중간 값과 key를 비교해가며 최종적으로 값을 찾음

50 "55" 60

남은 데이터(3개) 중에 중간값을 찾음 : 55
중간 값(=55)과 찾고자 하는 값(=55)을 비교함

 

- 어쨌든 binarySearch 메소드를 사용하려면 오름차순 정렬이 먼저 되어 있어야 하고 sort 메소드 등을 통해 오름차순 정렬을 수행하면 됨

    * 애초에 처음부터 데이터가 새로 들어올 때마다 원래 있던 데이터들과 값을 비교해서

       차곡차곡 오름차순으로 저장되도록 코드를 짜는 것도 괜찮지 않을까..

 

 

- [인스턴스가 저장된 배열]을 대상으로도 binarySearch 메소드를 호출할 수 있음

   → 예시 코드

public class NumberSearch implements Comparable {
	private int number;
	
	// setter
	NumberSearch(int num) {
		number = num;
	}
    ...
	// getter
	public int getNumber() {
		return number;
	}
	
	public int compareTo(Object obj) {
		NumberSearch n = (NumberSearch)obj;
		return this.number - n.number;
	}
}

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		NumberSearch[] numbers = new NumberSearch[5];
		NumberSearch key = new NumberSearch(49); // 찾고자 하는 값은 "49"
		
		numbers[0] = new NumberSearch(3);
		numbers[1] = new NumberSearch(55);
		numbers[2] = new NumberSearch(10);
		numbers[3] = new NumberSearch(27);
		numbers[4] = new NumberSearch(49);
		
		// 데이터를 먼저 오름차순 정렬함
		Arrays.sort(numbers);
	
		// binarySearch의 매개변수는 모두 Object 타입이어야 함
		// 반환값은 찾고자 하는 값이 있으면 인덱스(찾고자 하는 값의 위치)를 
		// 없으면 0보다 작은 수를 반환
		int index = Arrays.binarySearch(numbers, key);
		System.out.println("인덱스 "+index);
		System.out.println("찾는 값 "+numbers[index].getNumber());
	}
}

   → 실행결과는 다음과 같음

         * 오름차순 정렬을 한 후 이진탐색을 했기 때문에 인덱스는 3이 됨 (첫번째 요소의 인덱스는 0임)

 

- 유의할 점은 binarySearch 메소드가 key 값을 찾는 방법은 "compareTo" 메소드를 체크한다는 점임

   → 가령 위의 예시 코드에서 NumberSearch 클래스에 멤버변수 name을 추가했다고 가정

public class NumberSearch implements Comparable {
	private String name;
	private int number;
	...

   → 최종 목표는 (이름은 체크하지 않고) number가 "49"인 인스턴스를 찾는것이 목표라고 가정

         * 따라서 compareTo는 아래와 같이 오버라이딩

public int compareTo(Object obj) {
	NumberSearch n = (NumberSearch)obj;
	return this.number - n.number;
}

   → 메인 메소드는 아래와 같이 객체를 생성했다고 가정

...
NumberSearch[] numbers = new NumberSearch[3];

numbers[0] = new NumberSearch("Kim", 3);
numbers[1] = new NumberSearch("Choi", 27);
numbers[2] = new NumberSearch("Jang", 49);

   → binarySearch 메소드의 매개변수는 객체(Object) 타입이기 때문에 찾고자 하는 값도 인스턴스로 만들어줘야함

         * 인스턴스 변수 name은 "No-name"으로 초기화하고, 인스턴스 변수 number는 "49"로 초기화 했다고 가정 

NumberSearch key = new NumberSearch("No-name", 49);

   → 그리고 binarySearch 메소드를 실행해보면 인덱스로 "2"가 출력됨 (첫번째 요소는 인덱스가 0임)

System.out.println("인덱스 값은 "+Arrays.binarySearch(numbers, key)+"입니다");

 

- 인스턴스 변수 "name"이 일치하지 않기 때문에 (탐색 대상에는 "Jang"으로 되어 있고, key에는 "No-name"으로 되어 있음)

   "찾고자 하는 값이 존재하지 않는다"고 결과를 출력할 듯 하지만, 그렇지 않음

numbers[2] = new NumberSearch("Jang", 49) 과
NumberSearch key = new NumberSearch("No-name", 49)

- 그 이유는 binarySearch 메소드가 key 값을 탐색 대상에서 찾을 때는 compareTo 메소드를 이용하기 때문

   → 즉, 이런식으로 진행됨

        * numbers의 중간 인스턴스를 찾음 (= numbers[1]이 중간 값이 될 것임)

        * numbers[1]과 key 인스턴스를 인자로 해서 compareTo 메소드를 실행함

        * 이때, 오버라이딩 했던 compareTo 메소드를 보면 인스턴스 변수 "number"의 값만 비교하도록 코드로 구현했었음

public int compareTo(Object obj) {
	NumberSearch n = (NumberSearch)obj;
	return this.number - n.number;
}

        * 따라서, 인스턴스 변수 "name"은 비교하지 않고, 인스턴스 변수 "number"의 값만 비교함

   → 만약 "name"의 값과 "number"의 값을 모두 비교하며 탐색하고 싶다면 compareTo 메소드의 코드를 name도 비교하도록 수정하면 됨