자료구조와 함께 배우는 알고리즘 입문 자바편 3장 연습문제

Q1. 실습 3-3의 seqSearchSen 메서드를 for문을 사용하여 프로그램을 작성하세요.

import java.util.Scanner;
 
public class Main {
    
    static int seqsearch(int[]a, int key, int n) {
        for(int i = 0; i<n; i++) {
            if(a[i]==key)
                return i;
        }return -1;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("요솟수:");
        int n = sc.nextInt();
        int[]arr = new int[n];
        for(int i = 0; i<n; i++) {
            System.out.print("arr["+i+"]: ");
            arr[i] = sc.nextInt();
        }
        System.out.print("Key값: ");
        int key = sc.nextInt();
        int idx = seqsearch(arr, key, n);
        
        if(idx != -1) {
            System.out.println("찾고자 하는 요소 값은 arr["+idx+"]에 있습니다.");
        }else {
            System.out.println("찾고자 하는 값이 배열 안에 존재하지 않습니다.");
        }
    }
 
}

Q2. 선형 검색의 스캐닝 과정을 자세히 출력하는 프로그램을 작성하세요.

import java.util.Scanner;
 
public class Main {
    
    static int seqsearch(int[]a, int key, int n) {
        
        for(int i = 0; i<n; i++) {
            if(a[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char star = '*';
        String nbsp = "";
        int[]arr = {6, 4, 3, 2, 1, 9 ,8 };
        int n = arr.length;
        System.out.print("Key값:");
        int key = sc.nextInt();
        
        System.out.println("  |0 1 2 3 4 5 6 ");
        System.out.println("--+-----------------");
        int idx = seqsearch(arr,key,n);
        if(idx != -1) {
            for(int i = 0; i<idx+1; i++) {
                System.out.print("  |"+nbsp+star+"\n");
                System.out.print(" "+i+"|");
                for(int j = 0; j<arr.length; j++) {
                    System.out.print(arr[j]+" ");
                }
                System.out.println(" ");
                nbsp+= "  ";
            }
            System.out.println("그 값은 arr["+idx+"]에 있습니다.");
        }else {
            System.out.println("그 값은 배열에 존재하지 않습니다.");
        
        }
 
    }
 
}

Q3. 요솟수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장하고, 일치하는 요솟수를 반환하는 메서드를 작성하세요.

import java.util.Scanner;
 
public class Main {
    static int searchIdx(int[]a, int n , int key, int[]idx) {
        int index = 0;
        for(int i = 0; i< n; i++) {
            if(a[i] == key) {
                idx[index] =  i;
                index++;
            }
        }
        return index;
    
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("요솟수: ");
        int n = sc.nextInt();
        int[]arr = new int[n];
        int[]idx = new int[n];
        for(int i = 0 ; i< n; i++) {
            System.out.print("arr["+i+"]: ");
            arr[i] = sc.nextInt();
        }
        System.out.print("Key값: ");
        int key = sc.nextInt();
        
        int idxlength = searchIdx(arr,n,key,idx);
        System.out.println(idxlength);
        for(int i : idx) {
            System.out.print(i+" ");
        }
        
 
    }
 
}

Q4. 이진 검색의 과정을 자세히 출력하는 프로그램을 작성하세요.

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void space(int n) {
        for(int i = 0; i<n; i++) {
            System.out.print("  ");
        }
    }
 
    public static void binSearch(int[] a, int n, int key) {
        int pl = 0;
        int pr = n - 1;
        String left_arrow = "<-";
        String right_arrow = "->";
        char flag = '+';
        while(pl<=pr) {
            int pc = (pl + pr) / 2;
            System.out.print("  |"+left_arrow);
            space(pc);
            System.out.print(flag);
            space(pc);
            System.out.print(right_arrow+"\n");
            System.out.println(" "+pc+"| 1 2 3 5 6 8 9");
            if(a[pc] == key) {
                System.out.println("\n"+key+"는 x["+pc+"]에 있습니다.");
                break;
            }else if(a[pc]>key) {
                pr = pc-1;
            }else {
                pl = pc+1;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("key: ");
        int key = sc.nextInt();
        int[]arr = {1,2,3,5,6,8,9};
        int n = arr.length;
        System.out.println("  | 0 1 2 3 4 5 6");
        System.out.println("--+-----------------");
        binSearch(arr,n,key);
    }
 
}

Q5. 키 값과 일치하는 맨 앞의 요소를 찾는 binSearchX 메서드를 작성하세요.

public class Main {
 
    static int binSearchX(int[]a, int n, int key) {
        int pl = 0;
        int pr = n-1;
        int front = a.length;
        do {
            int pc = (pl + pr) / 2;
            if(a[pc]==key) {
                    front = pc;
                    for(int i = pc; i>0; i--) {
                        if(a[i]==key) {
                            if(front>i) {
                                front=i;        
                            }
                        }
                    }
                    return front;
                }
            
            else if(a[pc] > key) {
                pr = pc-1;
            }else{
                pl = pc+1;
            }
        }while(pl<=pr);return-1;
 
    }
 
    public static void main(String[] args) {
        int[]arr = {1,3,5,7,7,7,8,8,9,9};
        int key = 8;
        int n = arr.length;
        System.out.println(key+"는 x["+binSearchX(arr,n,key)+"]에 있습니다.");
 
    }
 
}

Q6. 검색에 실패하였을 때 삽입 포인트의 값을 출력하는 프로그램을 작성하세요.

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("요솟수: ");
        int n = sc.nextInt();
        System.out.println("오름차순으로 입력하세여.");
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            System.out.print("x[" + i + "]: ");
            arr[i] = sc.nextInt();
        }
        System.out.print("검색할 값: ");
        int key = sc.nextInt();
        int idx = Arrays.binarySearch(arr, key);
        if (idx < 0) {
            idx = -idx+-1;
            System.out.println("삽입 포인트: "+idx);
        } else {
            System.out.println("그 값은 x[" + idx + "]에 있습니다.");
        }
    }
 
}
 

Q7. 시력을 내림차순으로 정렬한 신체검사 데이터에서 특정 시력을 가진 사람을 검색하는 프로그램을 작성하세요.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
 
    static class PhyscData {
        private String name;
        private int height;
        private double vision;
        
        
        public PhyscData(String name, int height, double vision) {
            this.name = name;
            this.height = height;
            this.vision = vision;
        }
        public String toString() {
            return "이름: "+this.name + " 키: "+ this.height+" 시력: "+this.vision;
        }
        private static class VisionOrderComparator implements Comparator<PhyscData>{
            public int compare(PhyscData d1, PhyscData d2) {
                return (d1.vision < d2.vision) ? 1:
                    (d1.vision > d2.vision) ? -1:0;
            }
        }
        public static final Comparator<PhyscData>VISION_ORDER = 
                new VisionOrderComparator();
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PhyscData[] x = {
                new PhyscData("강민하", 162, 1.3),
                new PhyscData("이수연", 168, 1.2),
                new PhyscData("최준영", 169, 1.1),
                new PhyscData("장선우", 172, 1.0),
                new PhyscData("정신영", 178, 0.7),
                new PhyscData("김기영", 183, 0.2)    
        };
        System.out.print("찾고자하는 시력이 몇 입니까?: ");
        double vision = sc.nextDouble();
        int idx = Arrays.binarySearch(x,new PhyscData("",0,vision),PhyscData.VISION_ORDER);
        
        if(idx < 0) {
            System.out.println("그 값의 요소가 없습니다.");
        }else {
            System.out.println("그 값은 x["+idx+"]에 있습니다.");
            System.out.println("찾은 데이터: "+x[idx]);
        }
    }
 
}