코딩 테스트 Java 정렬 문제 풀이

선택 정렬 알고리즘 작성하기

해당 숫자들을 선택 정렬을 사용해서 정렬한 값을 출력하시오

 

6

13 5 11 7 23 15

---

풀이

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

public class 선택정렬 {
    public static void main(String[] args) {
        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 i=0; i<n-1; i++){
            int idx=i;
            //찾고자 하는 인덱스보다 +1값부터
            //가장 작은 수를 찾는다. 그리고 그 값을
            //해당 인덱스와 교환한다.
            for(int j=i+1; j<n; j++){
                if(arr[j]<arr[idx]) idx=j;
            }
            int tmp=arr[i];
            arr[i]=arr[idx];
            arr[idx]=tmp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

버블 정렬 알고리즘 작성하기

해당 숫자들을 버블 정렬을 사용해서 정렬한 값을 출력하시오

6

13 5 11 7 23 15

---

풀이

이웃한 두수 비교해서 앞이 크고 뒤가 작으면 바꿔준다.

이 패턴을 한번 돌고 나면 맨 뒤에 가장 큰 수가 위치한다.

맨 뒤에 수는 빼고 나머지 수를 대상으로 이웃 두수 비교해서 두 번째 큰수를 뒤에서 두 번째 인덱스에 위치 시킨다.

이런 식으로 버블 정렬을 완성한다.

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

public class 버블정렬 {

    public static void main(String[] args) {
        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();

        //i가 0일 때는 맨뒤의 가장 큰수를 구하는 for문이 된다.
        for(int i=0; i<n-1; i++){
            for(int j=0; j<n-i-1; j++){
                System.out.println(i+" "+ j);
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
    }
}

00
[5, 13, 11, 7, 23, 15]
01
[5, 11, 13, 7, 23, 15]
02
[5, 11, 7, 13, 23, 15]
03
[5, 11, 7, 13, 23, 15]
04
[5, 11, 7, 13, 15, 23]
10
[5, 11, 7, 13, 15, 23]
11
[5, 7, 11, 13, 15, 23]
12
[5, 7, 11, 13, 15, 23]
13
[5, 7, 11, 13, 15, 23]
20
[5, 7, 11, 13, 15, 23]
21
[5, 7, 11, 13, 15, 23]
22
[5, 7, 11, 13, 15, 23]
30
[5, 7, 11, 13, 15, 23]
31
[5, 7, 11, 13, 15, 23]
40
[5, 7, 11, 13, 15, 23]

삽입 정렬

해당 숫자들을 삽입 정렬을 사용해서 정렬한 값을 출력하시오

6

13 5 11 7 23 15

---

풀이

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

public class 삽입정렬 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        //삽입 정렬 시작
        for(int i=1; i<n; i++) {
            int tmp = arr[i], j;
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > tmp)
                    arr[j + 1] = arr[j];
                else
                    break;
            }
            arr[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

Least Recently Used 캐시 메모리

5 9 1 2 3 2 6 2 3 5 7

---

풀이

import java.util.Scanner;

public class LeastRecentlyUsed {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] cache = new int[size];

        for (int x : arr) {
            int pos = -1;
            //먼저 히트 값이 있는 지 찾는다.
            for (int i = 0; i < size; i++) {
                if (x == cache[i]) {
                    pos = i;
                }
            }
            //만약 히트 된 값이 없다면 cache[0] = 새로운 값 x를 넣어주고
            // 1번 인덱스 부터 오른쪽으로 이동한다.
            // 그러면 5번 인덱스는 size 밖으로 나가서 사라진다.
            if (pos == -1) {
                for (int i = size - 1; i >= 1; i--) {
                    cache[i] = cache[i - 1];
                }
                cache[0] = x;
            } else {
                //만약 히트된 값이 있다면
                //1번 인덱스부터 히트된 위치까지 오른쪽으로 이동한다
                for (int i = pos; i >= 1; i--) {
                    cache[i] = cache[i - 1];
                }
                cache[0] = x;
            }
        }
        System.out.println(Arrays.toString(cache));
    }
}

좌표 정렬

5 2 7 1 3 1 2 2 5 3 6

---

풀이

Point Class int x 값을 기준으로 오름차순 정렬한다고 하면 Comparable retrun 값을 this.x-o.x 로 설정해야 한다.

Comparable을 return 결정하는 방법은 retrun 값을 음수로 만드는 조건을 입력하는 것이다.

int가 오름차순으로 되어 있으면 예를 들어 {1, 3, 5, 7} 이 있다.

그러면 this 앞에 있는 값에서 o 뒤의 있는 값을 빼야 음수가 나온다.

그래서 오름 차순 정렬은 this.x- o.x가 되는 것이다.

반대로 내림차순으로 정렬할 때는 뒤에 값에서 앞의 값을 빼야 음수가 나오기 때문에 retrun o.x- this.x을 설정해야 한다.

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

public class 좌표정렬 {

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

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                "x=" + x +
                ", y=" + y +
                '}';
        }

        @Override
        public int compareTo(Point o) {
            if (this.x == o.x) {
                return this.y - o.y;
            }
            return this.x-o.x;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Point[] arr = new Point[n];
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            arr[i] = new Point(x, y);
        }
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        //[Point{x=1, y=2}, Point{x=1, y=3}, Point{x=2, y=5}, Point{x=2, y=7}, Point{x=3, y=6}]
    }
}

이분 검색

8 32 23 87 65 12 57 32 99 81

---

풀이

순차 검색은 배열 안 모든 원소들을 뒤져가면서 찾지만,

이분 검색은 이미 정렬되어 있는 배열을 반으로 잘라가면서 찾기 때문에 더 빠르게 검색을 할 수 있다.

먼저 찾고자 하는 값이 들어 있는 배열은 0번 인덱스를 lt 끝 인덱스를 rt로 설정한다.

그리고 lt가 rt보다 작거나 같은 상황까지 while문을 돌린다.

while문 안에는 mid 값이 존재해서(lt+rt/2) 해당 arr[mid] == 찾는 값과 같다면 while문을 종료해서 찾고자 하는 값의 인덱스를 발견한다.

만약 mid의 값이 찾고자 하는 값보다 크다면 arr의 왼쪽을 찾아야 하기 때문에 rt를 mid-1 값으로 설정한다.

찾고자 하는 값보다 작다면 arr 오른쪽을 찾아야 하기 때문에 lt를 mid+1 값으로 설정한다.

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

public class 이분검색 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int lt = 0;
        int rt = arr.length-1;
        int answer = 0;

        //이분 검색을 위한 많이 사용하는 코드 형싱이다.
        while(lt<=rt){
            int mid=(lt+rt)/2;
            if(arr[mid]==m){
                answer=mid+1;
                break;
            }
            //mid 인덱스 값이 찾고자 하는 값보다 크면 왼쪽으로 이동
            if(arr[mid]>m) rt=mid-1;
            //찾고자 하는 값보다 작으면 오른쪽으로 mid 이동한다.
            else lt=mid+1;
        }
        System.out.println(answer);
    }
}