P-coding

이번에는 백준 24060번 문제를 통해 병합 정렬 개념을 다시 다져보자.
이번 문제도 저번 개념 정리와 같이 재귀 방식으로 계속 나누고 
병합하며 정렬한다.

🔍 문제 핵심

• 병합 정렬은 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방법을 사용한다.
• 주어진 배열을 계속해서 절반으로 나누고, 더 이상 나눌 수 없을 때까지 나눈 뒤, 정렬된 상태로 병합한다.
• 문제에서 예시로 주어진 병합 정렬 과정을 잘 이해하고, 이를 직접 구현해보는 것이 핵심이다.

📌 병합 정렬이란?

1. 분할 (Divide)

• 배열을 절반으로 나눈다.
• 이 과정을 배열의 크기가 1이 될 때까지 반복한다.
• 각 하위 배열은 재귀적으로 처리된다.

2. 정복 (Conquer)

• 크기가 1인 배열끼리 **두 개씩 병합(Merge)**하며 정렬해나간다.
• 병합 과정에서 두 배열의 원소를 비교하여 작은 값을 먼저 넣는 방식으로 정렬이 이루어진다.

3. 병합 (Combine)

• 정렬된 두 배열을 하나로 합치며 정렬을 유지한다.

재귀 방식으로 정렬하는 복잡한 구조로 공부하기 좋은 문제이다.
이해도를 높이기 위해 많은 관련 문제를 푸는 것을 추천한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static int count = 0;
    private static int number = -1;
    private static int K;

    private static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1;
        int z = 0;

        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[z++] = arr[i++];
            }
            else {
                temp[z++] = arr[j++];
            }

        }

        while(i <= mid) {
            temp[z++] = arr[i++];
        }

        while(j <= right) {
            temp[z++] = arr[j++];
        }


        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
            count++;
            if(count == K) {
                number = temp[l];
            }
        }


    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        K = Integer.parseInt(stringTokenizer.nextToken());

        int[] arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        mergeSort(arr, 0, N - 1);

        System.out.println(number);

    }
}

이번에는 백준 4779번 문제를 통해 분할 정복의 개념을 다져보자.

칸토어 집합이란 간략히 설명하면
세 개로 분할하여 가운데를 제거해 나가는 작업을 반복하여 결과를 얻는 집합이다.

두 개로 나누었던 병합 정렬을 활용하면 풀어낼 수 있다.

문제 핵심

• 3의 N제곱 길이 만큼의 '-'가 반복된 문자열
• 3등분 하여 가운데를 공백으로 바꾼다.
  • 이 과정을 선의 길이가 1일 때 까지 반복

풀이 과정

합병 정렬을 이용하여 재귀를 통해 3등분 하여 처리한다.

반환 조건은 길이가 1일 때 반환한다.

핵심 코드

1. 길이가 1일 때 반환한다.
2. 크기를 3등분 한다.
3. 중간지점 부분을 모두 공백으로 바꾼다.
   1. 시작점 + 크기 = 중간지점의 시작점
   2. 시작점 + ( 2 * 크기 ) = 세번째 지점 시작점
4. 왼쪽 부분 재귀 실행
5. 오른쪽 부분 재귀 실행

private static void can(char[] arr, int start, int size) {
    if(size <= 1 ) {
        return;
    }

    int onePerThird = size / 3;

    for(int i = start + onePerThird; i < start + 2 * onePerThird; i++) {
        arr[i] = ' ';
    }

    can(arr, start, onePerThird);
    can(arr, start + 2 * onePerThird, onePerThird);
}

합병 정렬만 활용한다면 바로 풀 수 있는 쉬운 문제이다.
분할하여 재귀방식으로 풀어나가는 문제로 길이만 유의하여 코드를 작성하면 되겠다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static void can(char[] arr, int start, int size) {
        if(size <= 1 ) {
            return;
        }

        int onePerThird = size / 3;

        for(int i = start + onePerThird; i < start + 2 * onePerThird; i++) {
            arr[i] = ' ';
        }

        can(arr, start, onePerThird);
        can(arr, start + 2 * onePerThird, onePerThird);
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        while (true) {
            String input = br.readLine();
            if (input == null || input.isBlank()) {
                break;
            }

            int n = Integer.parseInt(input);
            if(n == 0) {
                stringBuilder.append("-\n");
                continue;
            }

            int size = (int) Math.pow(3, n);

            char[] result = new char[size];

            for (int i = 0; i < size; i++) {
                result[i] = '-';
            }

            can(result,0, size);
            stringBuilder.append(result).append('\n');
        }

        System.out.println(stringBuilder);
    }
}