[JAVA] 검색 (2)

자료구조와 함께 배우는 알고리즘 입문 - 자바편

책 보면서 차근차근 공부하는 중

---

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도
1. 시간 복잡도 (time complexity) 실행에 필요한 시간 평가
2. 공간 복잡도 (space complexity) 기억 영역과 파일 공간이 얼마나 필요한가를 평가

O(f(n))+O(g(n))=O(max(f(n),g(n))

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선한다
O(1)+O(n)+O(n)+O(1)+O(n)+O(1)
= O(max(1,n,n,1,n,1)) = O(n)

연습문제 1

    public static int seqSearch(int[] a,int num, int ky){
    
        for(int i=0;i<num;i++){
            if(a[i]==ky){
                return i;
            }
        }
        return -1;
    }

연습문제 3

import java.util.Scanner;

public class Main {
    public static int search(int[] a ,int n ,int key, int[] idx)
    {
        int num = 0 ;
        for(int i=0;i<n;i++){
            if(a[i]==key){
                idx[num]=i;
                num++;
            }
        }
        return num;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int []arr = new int [num];
        int []index = new int [num];

        int key = sc.nextInt();

        for(int i=0;i<num;i++){
            arr[i]=sc.nextInt();
        }
        int result = search(arr,num,key,index);
        System.out.print(result);
    }
}

연습문제 5

import java.util.Scanner;

public class Main {
    public static int binSearchX(int[] a, int n, int key){
        int middle = n/2;
        while(true){
            if(a[middle]==key){
                middle-=1;
            }else{
                middle++;
                break;
            }
        }
        return middle;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int key = sc.nextInt();
        int [] a = new int[num];
        for(int i=0;i<num;i++){
            a[i]=sc.nextInt();
        }
        int result = binSearchX(a,num,key);
        System.out.println(result);
    }
}

---

Arrays.binarySearch에 의한 이진 검색

검색에 성공한 경우 :

• key와 일치하는 요소의 인덱스 반환
• 일치하는 요소가 여러개라면 무작위의 인덱스 반환

검색에 실패한 경우 :

• 삽입 포인트가 x라고 할 때 -x-1를 반환
• 만약 삽입 포인트가 5라면 -> -6 반환

연습문제 6

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int []x = new int [num];

        System.out.println("x[0]: ");
        x[0]=sc.nextInt();

        for(int i=1;i<num;i++){
            do{
                System.out.print("x["+i+"] : ");
                x[i]=sc.nextInt();
            }while(x[i]<x[i-1]);
        }

        int ky=sc.nextInt();

        int idx=Arrays.binarySearch(x,ky);

        System.out.println(idx);
    }
}

---

클래스 메서드와 인스턴스 메서드

인스턴스 메서드는 static X, 클래스 메서드는 static O

인스턴스 메서드 호출 시 : 클래스형 변수 이름, 메서드 이름
클래스 메서드 호출 시 : 클래스 이름, 메서드 이름

자연 정렬 (natural ordering)

문자열 정렬 : 텍스트 1, 텍스트 10, 텍스트 100, 텍스트 2, 텍스트21
자연 정렬 : 텍스트 1, 텍스트 2, 텍스트 10, 텍스트 21, 텍스트 100
-> 자연스러운 정렬을 하려면

class A implements Comparable<A>{
	public int compareTo(A c){
    // this가 c보다 크면,작으면 같으면~
    }
    	public boolean equals(Object c){
        //this가 c와 같으면 true, 같지 않으면 false
        }

연습문제 7

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    static class PhysicData{
        private String name;
        private int height;
        private double vision;

        PhysicData(String name,int height,double vision){
            this.name=name;
            this.height=height;
            this.vision=vision;
        }

        public String toString(){
            return name+" "+height+" "+vision;
        }

        public static final Comparator<PhysicData> Vision_ORDER=new VisionOrderComparator();

        private static class VisionOrderComparator implements Comparator<PhysicData>{
            public int compare(PhysicData d1, PhysicData d2){
                return (d1.vision<d2.vision) ? 1:(d1.vision>d2.vision)? -1:0;
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PhysicData[] x ={
                new PhysicData("이나령",162,0.3),
                new PhysicData("유치훈",168,0.4),
                new PhysicData("김한결",169,0.8),
                new PhysicData("홍준기",171,1.5),
                new PhysicData("전서현",173,0.7),
                new PhysicData("이호연",174,1.2),
                new PhysicData("이수민",175,2.0),
        };
        System.out.print("시력 몇? : ");
        double vision = sc.nextDouble();
        int idx= Arrays.binarySearch(
                x,//배열 x에서
                new PhysicData("",0,vision),
                PhysicData.Vision_ORDER
        );

        if(idx<0){
            System.out.println("요소가 없습니다.");
        }else{
            System.out.println("x["+idx+"]에 있습니다.");
            System.out.println("찾은 데이터 : "+x[idx]);
        }
    }
}