섹션6. Sorting and Searching(정렬, 이분검색과 결정알고리즘)

  

 

📚 정렬 / 이분검색 & 결정 알고리즘

 

 

 

선택 정렬

 

 

import java.util.*;
class Solution {
    public int[] solution(int n, int[] arr) {
       for(int i=0; i<n-1; i++){
           for(int j=i+1; j<n; j++){
               if(arr[i]>arr[j]) {
                   int tmp=arr[j];
                   arr[j]=arr[i];
                   arr[i]=tmp;
               }
           }
       }
       return arr;
    }
    public static void main(String[] args){
        Solution T=new Solution();
        Scanner kb = new Scanner(System.in);;
        int n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++) arr[i]=kb.nextInt();
        for(int x : T.solution(n,arr)) System.out.print(x+" ");
    }
}

 

 

버블 정렬

 

import java.util.*;
class Main {
    public int[] solution(int n, int[] arr) {
        int[] answer=new int[n];
        for(int i=0; i<n-1; i++){
            for(int j=0; j<arr.length-i-1; j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
        return arr;
    }
    public static void main(String[] args){
        Scanner kb=new Scanner(System.in);
        Main T=new Main();
        int n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
        	arr[i]=kb.nextInt();
        }
        for(int x:T.solution(n,arr)) System.out.print(x+" ");
    }
}

 

 

삽입 정렬

 

import java.util.*;
class Solution {
    public int[] solution(int n,int[] arr) {
        int j=0;
        for(int i=1; i<arr.length; i++){
            int target=arr[i];
            for(j=i-1; j>=0&&arr[j]>target; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j+1]=target;
        }
        return arr;
    }
    public static void main(String[] args){
        Scanner kb=new Scanner(System.in);
        Solution T=new Solution();
        int n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        for(int x:T.solution(n,arr)) System.out.print(x+" ");

    }
}

 

 

 

Least Recently Used ( LRU )

중복 확인

 

 

import java.util.Scanner;
import java.util.Arrays;
class Solution {
    public String solution(int n, int[] arr) {
        String answer="";
        Arrays.sort(arr);
        for(int i=0; i<n-1; i++){
            if(arr[i]==arr[i+1])
                return "D";
        }
        return "U";
    }

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Solution T = new Solution();
        int n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<arr.length; i++){
            arr[i]=kb.nextInt();
        }
        System.out.println(T.solution(n,arr));
    }
}

 

 

 

장난 꾸러기

 

 

 

 

 

 

좌표 정렬

 

 

 

 

 

 

이분 검색

 

 

그냥 배열 0번 index부터 검색해도 되는데, 이런 순차검색은

효율성이 떨어지기에 이분검색 사용

 

import java.util.Scanner;
import java.util.Arrays;
class Solution {
    public int solution(int n, int m, int[] arr){
        int answer=0;
        Arrays.sort(arr);
        int lt=0, rt=n-1;
        while(lt<=rt){
            int mid=(lt+rt)/2;
            if(arr[mid]==m) {
                answer = mid + 1; // mid는 index 번호니까 번째= index+1
                break;
            }else if(arr[mid]>m){
                rt=mid-1;
            }else
                lt=mid+1;
        }
        return answer;

    }

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Solution T = new Solution();
        int n=kb.nextInt();
        int m=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
        }
        System.out.println(T.solution(n,m,arr));
    }
}

 

 

 

뮤직비디오 ( 결정 알고리즘 )

마구간 정하기 ( 결정 알고리즘 )