Sorting and Searching -(2)

Sorting and Searching -(2)

6-3. 삽입 정렬 | 복습

import java.util.Scanner;

/*6-3. 삽입 정렬| 복습*/
public class Main1 {

    public int[] solution(int n, int[] arr) {

        for(int i = 1; i<n; i++) {
            int tmp = arr[i];
            int j;
            for(j = i-1; j>=0; j--) {
                if(arr[j] > tmp) {
                    //S집합 값을 U집합 쪽으로 밀기
                    arr[j+1] = arr[j];
                }else break; //삽입 지점 찾았으면 break
            }
            //멈춘 지점에서 tmp 값도 세팅
            arr[j+1] = tmp;
        }
        return arr;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        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 + " ");
    }
}

---

6-4. Least Recently Used

• 1) 캐시 미스 : 현재 작업x가 기존 캐시에 존재X
  • 이 경우, 맨 뒤(size-1)부터 0까지 거꾸로 돌면서
    • 기존 작업들을 뒤로 밀고
• 2) 캐시 히트 : 현재 작업x가 기존 캐시에 존재O
  • 이 경우, 히트 지점(pos)부터 0까지 거꾸로 돌면서
    • 기존 작업들을 뒤로 밀고
• 3) 무조건 현재 작업x를 맨 앞에 담음

import java.util.Scanner;

/* 6-4.Least Recently Used
[입력]
첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다.
두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다
[출력]
마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.
*/

public class Main2 {
    //솔루션 함수
    public int[] solution(int size, int n, int[] arr) {
        int[] cache = new int[size];
        //작업 하나씩 가져옴
        for(int x: arr) {
            //인덱스 찍을 변수 
            int pos = -1;
            //캐시 내부를 차례로 돌되
            for(int i = 0; i<size; i++) {
                //[Hit] arr에서 꺼낸 값이 캐쉬의 값에 존재할 경우 
                if(x==cache[i]) pos=i; //Hit 지점 인덱스를 pos에 저장시킴
            }
            //캐시 미스 (즉. 히트난 지점 없을 경우) 맨 뒤부터 거꾸로 돌면서 밀기
            if(pos == -1) {
                for(int i = size-1; i>=1; i--) {
                    //거꾸로 작업 밀어버림
                    cache[i] = cache[i-1];
                }
            }
            else { //캐시 히트 처리 (히트 지점부터 거꾸로 돌면서 밀기)
                for(int i = pos; i>=1; i--) {
                    //거꾸로 작업 밀어버림
                    cache[i] = cache[i-1];
                }
            }
            //무조건 맨 앞에는 현재 작업x 담음
            cache[0] = x;
        }
        return cache;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);

        int s = kb.nextInt();
        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(s, n, arr)) System.out.print(x+" ");
    }
}

---

6-5. 중복 확인

• 중복 확인은 HashMap 사용이 더 간단하고 효율 좋다
• 다만, 정렬로도 중복 확인 되는 것을 보여주기 위해 풀어보자
• 1) 먼저 정렬한다.
• 2) 이웃한 두 수가 같을 경우 중복이다. “D” 반환

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

/*6-5. 중복 확인 
[입력]
첫 번째 줄에 자연수 N(5<=N<=100,000)이 주어진다.
두 번째 줄에 학생들이 적어 낸 N개의 자연수가 입력된다.
[출력]
첫 번째 줄에 D 또는 U를 출력한다.
*/
public class Main3 {
    //솔루션 함수 
    public String solution(int n, int[] arr ) {
        String answer = "U";
        Arrays.sort(arr); //정렬
        for(int i = 0; i<n-1; i++) {
            //이웃한 두 수 같을 경우 중복
            if(arr[i] == arr[i+1]) {
                return "D";
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        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();

        System.out.println(T.solution(n, arr));
    }

}

---

6-6. 장난꾸러기

• 정렬 배열 vs 입력 배열을 for(i) 비교하며 다른 지점을 answer에 누적한다.

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

/* 6-6. 장난 꾸러기
[입력]
첫 번째 줄에 자연수 N(5<=N<=100)이 주어진다.
두 번째 줄에 제일 앞에부터 일렬로 서있는 학생들의 키가 주어진다.
키(높이) 값 H는 (120<=H<=180)의 자연수 입니다.
[출력]
첫 번째 줄에 철수의 반 번호와 짝꿍의 반 번호를 차례로 출력합니다.*/
public class Main4 {
    public ArrayList<Integer> solution(int n, int[] arr){
        ArrayList<Integer> answer= new ArrayList<>();
        //이 문제의 경우, 정상 정렬된 배열과 입력받은 배열을 for(i)로 각각 비교하며 
        //바뀐 지점 찾으면 되는 문제이다.
        //1) 정렬 전에 기존 arr를 임시 tmp에 깊은 복사 clone 떠놓고 
        int[] tmp = arr.clone();
        //2) 이제 tmp를 정렬한다.
        Arrays.sort(tmp);

        //3) 각 i 값 비교하여 다른 지점이 바뀐 지점
        for(int i = 0; i<n;i++) {
            if(arr[i] != tmp[i]) answer.add(i+1); //바뀐 지점 담기 
        }    
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Main4 T = new Main4();
        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 + " ");
    }
}

---

💡 **Comparable을 이용**하여 Java 객체를 정렬할 수 있다. **Comparator을 이용**하여 Java 객체를 정렬할 수 있다.

⬛ 객체 정렬

• 객체를 사용자가 정의한 정렬 기준에 맞춰 정렬해야 하는 경우
  • Ex) 좌표를 x좌표가 증가하는 순, x좌표가 같으면 y좌표가 감소하는 순으로 정렬
  • Ex) 국어점수는 증가하는 순, 수학점수는 감소하는 순으로 정렬

⬛ Comparable 인터페이스 사용

• 기본적으로 적용될 정렬 기준이 되는 메소드 정의하는 인터페이스
• [구현] 정렬할 객체에 Comparable interface를 implements 후, compareTo() 메서드를 오버라이드하여 구현한다.

🟪 compareTo() 메소드 사용법

• (1) 현재 개체 < 파라미터로 넘어온 객체 : 음수리턴
• (2) 현재 객체 == 파라미터로 넘어온 객체 : ‘0’ 리턴
• (3) 현재 객체 > 파라미터로 넘어온 객체 : 양수 리턴
• ⇒음수 or ‘0’ 이면, 객체의 자리가 그대로 유지
• ⇒ 양수이면, 두 객체 자리가 바뀐다.

🟪 Collection.sort() vs Arrays.sort() 차이

• (1) Collections.sort()
• • List.Collection 정렬의 경우
• Ex) ArrayList, LinkedList, Vector 등
• 내부적으로 Arrays.sort() 를 사

// x좌표가 증가하는 순, x좌표가 같으면 y좌표가 감소하는 순으로 정렬하라.
class Point implements Comparable<Point> {
    int x, y;

    @Override
    public int compareTo(Point p) {
        if(this.x > p.x) {
            return 1; // x에 대해서는 오름차순
        }
        else if(this.x == p.x) {
            if(this.y < p.y) { // y에 대해서는 내림차순
                return 1;
            }
        }
        return -1;
    }
}

// main에서 사용법
List<Point> pointList = new ArrayList<>();
pointList.add(new Point(x, y));
Collections.sort(pointList);
https://gmlwjd9405.github.io/2018/09/06/java-comparable-and-comparator.html

---

6-7. 좌표 정렬 | 객체 정렬 ***

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/* 6-7. 좌표 정렬
[입력]
첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.
두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.
[출력]
N개의 좌표를 정렬하여 출력하세요.*/

class Point implements Comparable<Point>{
    public int x, y;

    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    //재정의 - 이 객체를 어떤 조건으로 정렬해줄 것인지 재정의 (현재는 오름차순 정렬)
    @Override
    public int compareTo(Point obj) {
        //만약 x가 같을 경우, y 기준 정렬하고 
        if(this.x == obj.x) {
            return this.y - obj.y; //작은거-큰거
        }else {
            //아니면 x 기준 정렬한다. 
            return this.x - obj.x; //작은거-큰거
        }
    }
}
class Main5 {
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for(int i =0; i<n; i++) {
            int x = kb.nextInt();
            int y = kb.nextInt();
            arr.add(new Point(x, y)); //담고
        }
        //객체 기준 정렬
        Collections.sort(arr);
        //출력
        for(Point obj : arr) System.out.println(obj.x + " " + obj.y);
    }

}

---