코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

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

[나의 풀이]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

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

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

        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> list1 = new ArrayList<>();
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            list1.add(Integer.parseInt(st.nextToken()));
        }

        int k = Integer.parseInt(br.readLine());

        // 간격
        int div = n / k;

        ArrayList<Integer> ans = new ArrayList<>();

        for (int i = 0; i < n; i += div) {

            // subList : 파이썬의 인덱싱
            ArrayList<Integer> list2 = new ArrayList<>(list1.subList(i, i + div));
            Collections.sort(list2);

            // addAll : ArrayList에 자료구조 모든 데이터를 다 넣음
            ans.addAll(list2);
        }

        for (int i = 0; i < ans.size(); i++) {
            bw.write(ans.get(i) + " ");
        }

        bw.flush();

    }

}

[팀원의 풀이]

# coding = utf-8

import sys
input = sys.stdin.readline

n = int(input())
num_list = list(map(int,input().split()))
k = int(input())

def merge(ls1, ls2) :
    tmp = list()
    l, r = 0, 0
    while len(ls1) > l and len(ls2) > r :
        if ls1[l] > ls2[r] :
            tmp.append(ls2[r])
            r += 1
        else :
            tmp.append(ls1[l])
            l += 1
    tmp += ls1[l:]
    tmp += ls2[r:]
    return tmp

idx = n//2
print(idx)
while True :
    if idx < k :
        break
    leng = n//idx
    print(leng)
    for i in range(0,n-leng+1,leng) :
        left_ls = num_list[i:i+(leng//2)]
        right_ls = num_list[i+(leng//2):i+leng]
        print(left_ls, right_ls)
        num_list[i:i + leng] = merge(left_ls, right_ls)
        print(merge(left_ls, right_ls))
    idx //= 2
print(*num_list)

정렬/분할정복 알고리즘 문제입니다. 위 문제의 본 의도는 병합 정렬입니다. Merge 정렬의 특정 단계를 출력하는 문제인데 알고리즘 교재에서 공부한 내용이나 구글링해서 찾아본 소스들을 보면 문제에서 요구한 방법과 상이했습니다.

기본적으로 병합 정렬이라고 하면 맨처음에는 [a,b][c,d][e,f][g,h]..2개씩 쌍지어 정렬, 그 다음으로 [a,b,c,d][e,f,g,h] 4개씩 쌍지어 정렬...8개...16개...씩 정렬하는 방식입니다. 🙊🙊🙊

하지만 구글링해본 내용에 의하면 대부분 아래와 같이 [a,b]정렬, [c,d]정렬 ,[a,b,c,d]정렬,[a,b,c,d,e,f,g,h]정렬 하며 확장되는 방식이였습니다.

참고: 'Do it 자료구조와 함께하는 알고리즘 Java' 도서

import java.util.Arrays;

public class page243_merge_sort2 {

    static int[] buff;

    static void merge_sort1(int[] a, int n) {

        // 작업용 배열 buff
        buff = new int[n];

        merge_sort2(a, 0, n - 1);

        buff = null;
    }

    static void merge_sort2(int[] a, int left, int right) {

        if (left < right) {

            int i;
            int center = (left + right) / 2;
            int p = 0;
            int j = 0;
            int k = left;

            merge_sort2(a, left, center);
            merge_sort2(a, center + 1, right);

            for (i = left; i <= center; i++) {
                buff[p++] = a[i];

            }

            System.out.println("buff:" + Arrays.toString(buff));

            while (i <= right && j < p) {
                a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
            }

            while (j < p) {
                a[k++] = buff[j++];
            }
            System.out.println("a :" + Arrays.toString(a));

        }

    }

    public static void main(String[] args) {

        int[] a = new int[] { 6, 4, 3, 7, 1, 9, 8, 2 };

        merge_sort1(a, a.length);

    }

위처럼 병합 정렬이지만 문제에서 요구하는 방식과는 달라 병합 정렬의 특징 중 하나인 병합하면서 크기가 2배로 커지는 작업 ArrayList를 활용해 K명의 회원이 정렬하는 ArrayList만 계산하여 해결할 수 있었습니다.🐱🐱🐱

오늘 문제 모르는 내용을 구글링한 내용이 틀릴 수도 있구나라고 큰 깨달음을 얻은 문제였습니다... 심지어 네임드(?) 블로그였던것으로 기억합니다...💦💦💦

감사합니다!!!