230711 13주 2일차 TIL. 쿼드트리, 퀵소트, 이진탐색

쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

public class Boj1992 {
    // 입력에 대한 정보를 클래스 필드로 저장한다.
    // 입력된 0과 1로 구성된 이미지
    private char[][] image;
    // 결과를 저장하기 위한 StringBuilder
    public StringBuilder quadTreeBuilder;

    private void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        image = new char[n][];
        for (int i = 0; i < n; i++) {
            // String.toCharArray()를 사용하면 문자열을 char[]로 변환 가능
            image[i] = reader.readLine().toCharArray();
        }
        quadTreeBuilder = new StringBuilder();
        compressQuad(n, 0, 0);
        System.out.println(quadTreeBuilder.toString());
    }

    private void compressQuad(
            // n: 정사각형의 한변의 길이
            int n,
            // x: 정사각형의 시작 x index (사각형의 왼쪽 위 x좌표)
            int x,
            // y: 정사각형의 시작 y index (사각형의 왼쪽 위 y좌표)
            int y
    ) {
        // 조건을 만족했는지 검사하는 flag
        boolean success = true;
        // 모든 요소가 같지 않을 경우 success = false를 해준다.
        // x, y의 값을 저장해두고
        // x ~ x + n - 1, y ~ y + n - 1까지 반복하면서
        // 초기의 값과 달라지는지를 검사한다.
        char init = image[x][y];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (image[x + i][y + j] != init) {
                    success = false;
                    break;
                }
            }
            if (!success) break;
        }
        // 원소들 검사 후 success == false라면 쪼개서 재귀호출
        if (!success) {
            // 좌 괄호 입력
            quadTreeBuilder.append('(');
            // 4등분 하기 위한 half
            int half = n / 2;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    compressQuad(
                            half,
                            x + half * i,
                            y + half * j
                    );
                }
            }
            // 4등분 영상이 압축이 끝나면 우괄호 입력
            quadTreeBuilder.append(')');
        } else {
            // 모든 원소가 일치했다면 첫번째 검사한 원소를 입력
            quadTreeBuilder.append(init);
        }
    }

    public static void main(String[] args) throws IOException {
        new Boj1992().solution();
    }
}

 

퀵소트

public class QuickSort {
    public void sort(int[] arr) {
        // 비었거나 길이가 1 이하면 정렬할 필요 X
        if (arr == null || arr.length <= 1) {
            return ;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // quickSort 후 나눠진 index를 반환받는다.
            int pivot = partition(arr, low, high);

            // 해당 index를 기준으로 좌우에 대하여 다시
            // quicksort를 호출한다.
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    // pivot을 정하고, pivot을 기준으로 좌우 배열의 원소들을 교환한 뒤
    // pivot이 최종적으로 위치하는 곳을 반환하는 메소드
    private int partition(int[] arr, int low, int high) {
        // 오른쪽 끝이 pivot
        int pivot = arr[high];
        // 작은 원소가 들어갈 위치를 지정하는 i
        int i = low - 1;
        // j == low 부터 j == high -1 까지 반복 (pivot 제외 전부 대조)
        for (int j = low; j < high; j++) {
            // 현재 원소의 값이 pivot 보다 작은 경우
            if (arr[j] <= pivot) {
                i++;
                // 왼쪽 끝으로 보낸다.
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 이 과정이 끝나면 arr[i]에는 pivot 보다 작은 원소가,
        // i + 1 ~ high - 1의 모든 원소는 pivot 보다 큰 원소가 담겨있다.
        // i + 1과 pivot의 위치를 교환하면, i + 1을 기준으로
        // 왼쪽은 pivot보다 작은 값이
        // 오른쪽은 pivot보다 큰 값이 위치한다.
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // 마지막으로 pivot의 위치를 반환한다.
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 7, 4, 8, 6, 2, 5,};
        new QuickSort().sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

이진탐색

public class BinarySearch {
    public int binarySearch(int[] arr, int target) {
        // 검색범위를 한정하는 left right
        int left = 0;
        int right = arr.length - 1;

        // 왼쪽 index가 오른쪽 index보다 커지면 발견 실패
        while (left <= right) {
            // 현재 가운데 원소를 검색 대상과 비교
            int mid = left + (right - left) / 2;

            // 가운데서 발견: 검색 성공
            if (arr[mid] == target) return mid;
            // 찾는 숫자보다 지금 숫자가 작으면
            // mid 기준 오른쪽 구간을 대상으로 선정
            else if (arr[mid] < target) left = mid + 1;
            // 찾는 숫자보다 지금 숫자가 크면
            // mid 기준 왼쪽 구간을 대상으로 선정
            else right = mid - 1;
        }

        return -1;
   }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 11;
        int index = new BinarySearch().binarySearch(arr, target);

        if (index != -1) {
            System.out.println(index);
        } else {
            System.out.println("탐색 실패");
        }
    }
}