[25/4월 3주차] 진행 내용 (04/14 ~ 04/20)

[Sangtriever]

📅 이번 주 일정
날짜: 2025/04/07 ~ 2025/04/13

📋 진행 내용
Chapter4. 04-5 버블 소트 프로그램 2(1517)
Chapter4. 04-6 수 정렬하기3(10989)

📢 참고 사항
별도 커밋을 하지 않고, 이슈 내 댓글에 숙제를 올려주세요!
댓글 내 소스코드 작성 방법은 아래와 같습니다.

예시)

import java.util.Arrays;

public class Test{
    public static void main(String[] args) {
        System.out.println(Arrays.toString(players));
    }

    private static void swiping(String[] array, int i, int j) {
        String temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

복사해서 사용하세요!

🗣️ 질문/피드백
이번 주 일정이나 진행 내용에 대해 궁금한 점이나 피드백이 있다면 댓글로 남겨주세요.

[hongdangmoo49]

📋 문제 정보
Chapter4. 04-5 버블 소트 프로그램 2(1517)

🔍 풀이

export interface BubbleSortInput {
    n: number;
    numbers: number[];
  }
  
export const countBubbleSortSwaps = (input: BubbleSortInput): number => {
    const { numbers } = input;
    let swapCount = 0;
    
    const mergeSort = (arr: number[], left: number, right: number): number[] => {
      if (left >= right) {
        return [arr[left]];
      }
      
      const mid = Math.floor((left + right) / 2);
      const leftArr = mergeSort(arr, left, mid);
      const rightArr = mergeSort(arr, mid + 1, right);
      
      return merge(leftArr, rightArr);
    };
    
    const merge = (leftArr: number[], rightArr: number[]): number[] => {
      const result: number[] = [];
      let leftIndex = 0;
      let rightIndex = 0;
      
      while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        if (leftArr[leftIndex] <= rightArr[rightIndex]) {
          result.push(leftArr[leftIndex]);
          leftIndex++;
        } else {
          swapCount += leftArr.length - leftIndex;
          result.push(rightArr[rightIndex]);
          rightIndex++;
        }
      }
      
      while (leftIndex < leftArr.length) {
        result.push(leftArr[leftIndex]);
        leftIndex++;
      }
      
      while (rightIndex < rightArr.length) {
        result.push(rightArr[rightIndex]);
        rightIndex++;
      }
      
      return result;
    };
    
    mergeSort([...numbers], 0, numbers.length - 1);
    
    return swapCount;
  };

📋 문제 정보
Chapter4. 04-6 수 정렬하기3(10989)

🔍 풀이

export interface SortNumbersInput {
    n: number;
    numbers: number[];
  }
  
export const sortNumbers = (input: SortNumbersInput): number[] => {
    const { numbers } = input;
    
    const count = new Array(10001).fill(0);
    
    for (const num of numbers) {
      count[num]++;
    }
    
    const result: number[] = [];
    
    for (let i = 1; i <= 10000; i++) {
      while (count[i] > 0) {
        result.push(i);
        count[i]--;
      }
    }
    
    return result;
  };

[ingwang-kim]

📋 문제 정보
Chapter4. 04-5 버블 소트 프로그램 2(1517)

🔍 풀이

import java.io.*;

public class Main {
    static long count = 0;
    static int[] arr, tmp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        tmp = new int[n];

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        mergeSort(0, n - 1);
        System.out.println(count);
    }

    static void mergeSort(int start, int end) {
        if (start >= end) return;

        int mid = (start + end) / 2;
        mergeSort(start, mid);
        mergeSort(mid + 1, end);
        merge(start, mid, end);
    }

    static void merge(int start, int mid, int end) {
        int left = start;
        int right = mid + 1;
        int idx = start;

        while (left <= mid && right <= end) {
            if (arr[left] <= arr[right]) {
                tmp[idx++] = arr[left++];
            } else {
                tmp[idx++] = arr[right++];
                count += (mid - left + 1); 
            }
        }

        while (left <= mid) tmp[idx++] = arr[left++];
        while (right <= end) tmp[idx++] = arr[right++];

        for (int i = start; i <= end; i++) {
            arr[i] = tmp[i];
        }
    }
}

📋 문제 정보
Chapter4. 04-6 수 정렬하기3(10989)

🔍 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] count = new int[10001]; // 숫자 범위: 1 ~ 10000

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            count[num]++;
        }
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= 10000; i++) {
            for (int j = 0; j < count[i]; j++) {
                sb.append(i).append('\n');
            }
        }

        System.out.print(sb);
    }
}

[leemeo3]

📋 문제 정보
Chapter4. 04-5 버블 소트 프로그램 2(1517)

🔍 풀이

public class P21버블소트프로그램2 {
    public static int[] A, tmp;
    public static long result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        tmp = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        result = 0;
        merget_sort(1, N);
        System.out.println(result);
    }

    private static void merget_sort(int s, int e) {
        if (e - s < 1) {
            return;
        }
        int m = s + (e - s) / 2;
        merget_sort(s,  m);
        merget_sort(m + 1, e);
        for (int i = s; i <= e; i++) {
            tmp[i] = A[i];
        }
        int k = s;
        int index1 = s;
        int index2 = m + 1;
        while (index1 <= m && index2 <= e) {
            if (tmp[index1] > tmp[index2]) {
                A[k] = tmp[index2];
                result = result + index2 - k;
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

📋 문제 정보
Chapter4. 04-6 수 정렬하기3(10989)

🔍 풀이

public class P022수정렬하기3 {
    public static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        Radix_Sort(A, 5);
        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void Radix_Sort(int[] A, int max_size) {
        int[] output = new int[A.length];
        int result = 1;
        int count = 0;
        while (count != max_size) {
            int[] bucket = new int[10];
            for (int i = 0; i < A.length; i++) {
                bucket[(A[i] / result) % 10]++;
            }
            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1];
            }
            for (int i = A.length - 1; i >= 0; i--) {
                output[bucket[(A[i] / result % 10)] - 1] = A[i];
                bucket[(A[i] / result) % 10]--;
            }
            for (int i = 0; i < A.length; i++) {
                A[i] = output[i];
            }
            result = result * 10;
            count++;
        }
    }
}

[eunsol-an]

📋 문제 정보
문제 제목:04-5 버블 소트 프로그램 2(1517)

🔍 풀이

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

public class Main {
    public static int[] A, tmp;
    public static long result;

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

        int N = Integer.parseInt(br.readLine());
        A = new int[N + 1];
        tmp = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        result = 0;
        mergeSort(1, N);

        System.out.println(result);
    }

    private static void mergeSort(int s, int e) {
        if (e - s < 1) return;
        int m = s + (e - s) / 2;

        mergeSort(s, m);
        mergeSort(m + 1, e);

        for (int i = s; i <= e; i++) {
            tmp[i] = A[i];
        }

        int k = s;
        int index1 = s;
        int index2 = m + 1;

        while (index1 <= m && index2 <= e) {
            if (tmp[index1] > tmp[index2]) {
                A[k] = tmp[index2];
                result = result + index2 - k;
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }

    }
}

---

📋 문제 정보
문제 제목 : 04-6 수 정렬하기3(10989)

🔍 풀이

import java.io.*;

public class Main {
    public static int[] A;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        radixSort(A, 5);

        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static void radixSort(int[] A, int max_size) {
        int[] output = new int[A.length];
        int digit = 1;
        int count = 0;

        while (count != max_size) {
            int[] bucket = new int[10];
            for (int i = 0; i < A.length; i++) {
                bucket[(A[i] / digit) % 10]++;
            }
            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1];
            }
            for (int i = A.length - 1; i >= 0; i--) {
                output[bucket[(A[i] / digit % 10)] - 1] = A[i];
                bucket[(A[i] / digit) % 10]--;
            }
            for (int i = 0; i < A.length; i++) {
                A[i] = output[i];
            }
            digit = digit * 10;
            count++;
        }
    }
}

---

[woooo96]

📋 문제 정보
Chapter4. 04-5 버블 소트 프로그램 2(1517)

🔍 풀이

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

public class Main {
static long swapCount = 0; // swap 횟수를 저장할 변수 (long 주의!)
static int[] arr, temp;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    arr = new int[n];
    temp = new int[n];

    String[] input = br.readLine().split(" ");
    for (int i = 0; i < n; i++) {
        arr[i] = Integer.parseInt(input[i]);
    }

    mergeSort(0, n - 1);

    System.out.println(swapCount);
}

public static void mergeSort(int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        merge(left, mid, right);
    }
}

public static void merge(int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;

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

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

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

    for (int l = left; l <= right; l++) {
        arr[l] = temp[l];
    }
}

}

📋 문제 정보
Chapter4. 04-6 수 정렬하기3(10989)

🔍 풀이

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

public class Main {
public static void main(String[] args) throws IOException {
final int MAX = 10000;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

    int[] count = new int[MAX + 1]; 


    for (int i = 0; i < n; i++) {
        int num = Integer.parseInt(br.readLine());
        count[num]++;
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= MAX; i++) {
        while (count[i]-- > 0) {
            sb.append(i).append('\n');
        }
    }

    System.out.print(sb);
}

}

[Sangtriever]

📋 문제 정보
문제 제목:04-5 버블 소트 프로그램 2(1517)

🔍 풀이

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

public class Main {
    static int[] numbers;    
    static int[] sorted;      
    static long swapCount = 0; 

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


        int n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        sorted = new int[n]; 

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        mergeSort(0, n - 1);

        System.out.println(swapCount);
    }

    // 병합 정렬
    private static void mergeSort(int left, int right) {
        if (left >= right) return;

        int mid = (left + right) / 2;

        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        merge(left, mid, right);
    }

    private static void merge(int left, int mid, int right) {
        int i = left;
        int j = mid + 1; 
        int idx = left;

        while (i <= mid && j <= right) {
            if (numbers[i] <= numbers[j]) {
                sorted[idx++] = numbers[i++];
            } else {
                sorted[idx++] = numbers[j++];
                swapCount += (mid - i + 1); 
            }
        }

        while (i <= mid) {
            sorted[idx++] = numbers[i++];
        }
        while (j <= right)) { 
           sorted[idx++] = numbers[j++];
        }
        for (int k = left; k <= right; k++) {
            numbers[k] = sorted[k];
        }
    }
}

📋 문제 정보
문제 제목 : 04-6 수 정렬하기3(10989)

🔍 풀이

    
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
		int n = Integer.parseInt(br.readLine());
		int[] list= new int[N];
        
		for(int i = 0; i < n; i++){
			list[i] = Integer.parseInt(br.readLine());
		}
        
		Arrays.sort(arr);
        
		for(int i = 0; i < n; i++){
			sb.append(list[i]).append('\n');
		}
 
		System.out.println(sb);
	}

[kyuung09]

📋 문제 정보
Chapter4. 04-5 버블 소트 프로그램 2(1517)

🔍 풀이

import java.io.*;
import java.util.*;

public class Main {
    static long swapCount = 0;
    static int[] arr, temp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        temp = new int[N];

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

        mergeSort(0, N - 1);

        System.out.println(swapCount);
    }

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

            mergeSort(left, mid);
            mergeSort(mid + 1, right);

            merge(left, mid, right);
        }
    }

    static void merge(int left, int mid, int right) {
        int i = left;    
        int j = mid + 1; 
        int k = left;  

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                swapCount += (mid - i + 1);  // i부터 mid까지는 모두 arr[j]보다 큼 → swap 발생
            }
        }

        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        for (int idx = left; idx <= right; idx++) {
            arr[idx] = temp[idx];
        }
    }
}

📋 문제 정보
Chapter4. 04-6 수 정렬하기3(10989)

🔍 풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        final int MAX = 10000;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] count = new int[MAX + 1]; // 1~10000까지

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            count[num]++;
        }

        for (int i = 1; i <= MAX; i++) {
            while (count[i]-- > 0) {
                bw.write(i + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}