문제

실수로 워밍업 클럽 출석을 빼먹었는데 우연히 데이터를 수정할 수 있는 권한이 주어졌습니다. 러너분의 이름(name)과 출석수(count)가 저장된 배열에서 여러분(나)의 데이터를 퀵정렬을 이용해 오름차순 정렬하고 가장 첫 번째 데이터인 여러분의 출석수를 변경하도록 코드를 작성해주세요. (퀵정렬 구현 부분도 변경)

// 퀵소트 구현 부분...(생략)

let user1 = {
    name: "홍길동",
    count: 5
};

let user2 = {
    name: "임꺽정",
    count: 4
}

let user3 = {
    name: "이순신",
    count: 3
}

let user4 = {
    name: "나",
    count: 1
}

let user5 = {
    name: "짱구",
    count: 5
}

let arr = [user1, user2, user3, user4, user5]

console.log("===== 정렬 전 =====");
console.log(arr);

quickSort(arr, 0, arr.length - 1);

console.log("===== 정렬 후 =====");
console.log(arr);

예상 결과

===== 정렬 전 =====
[
  { name: '홍길동', count: 5 },
  { name: '임꺽정', count: 4 },
  { name: '이순신', count: 3 },
  { name: '나', count: 1 },
  { name: '짱구', count: 5 }
]
===== 정렬 후 =====
[
  { name: '나', count: 5 },
  { name: '이순신', count: 3 },
  { name: '임꺽정', count: 4 },
  { name: '홍길동', count: 5 },
  { name: '짱구', count: 5 }
]

문제 해결

[깃허브 코드 - Java로 작성]

1. 이전에 작성한 퀵소트 정렬 코드 참고하기

2. 다른 점

   1. 숫자 배열이 아닌 객체 배열을 만들어야 한다.

   2. 객체 배열 안에서 count 로 오름차순을 한다.

3. 첫 번째 해결 - count로 오름차순하기

   1. name과 count를 함께 저장할 수 있는 Runner 클래스 생성

   2. 이전 코드에서 int[] 배열 대신 Runner[] 배열로 변경

package sectionThree.quickSort.specialMission;

public class Runner {
    private String name;
    private int count;

    public Runner(String name, int count) {
        this.name = name;
        this.count = count;
    }

    public int getCount() {
        return count;
    }

    @Override
    public String toString() {
        return "{name: '" + name + "', count: " + count + '}';
    }
}

package sectionThree.quickSort.specialMission;

import java.util.Arrays;

public class QuickSortMission {
    public static void quickSortM(Runner[] runners, int left, int right) {
        if (left <= right) {
            int pivot = divideM(runners, left, right);

            quickSortM(runners, left, pivot - 1);
            quickSortM(runners, pivot + 1, right);
        }
    }

    public static int divideM(Runner[] runners, int left, int right) {
        int pivot = runners[left].getCount();
        int leftStartIndex = left + 1;
        int rightStartIndex = right;

        while (leftStartIndex <= rightStartIndex) {

            while (leftStartIndex <= right && pivot >= runners[leftStartIndex].getCount()) {
                leftStartIndex++;
            }

            while (rightStartIndex >= (left + 1) && pivot <= runners[rightStartIndex].getCount()) {
                rightStartIndex--;
            }

            if (leftStartIndex <= rightStartIndex) {
                swapM(runners, leftStartIndex, rightStartIndex);
            }
        }

        swapM(runners, left, rightStartIndex);
        return rightStartIndex;
    }

    public static void swapM(Runner[] runners, int index1, int index2) {
        Runner temp = runners[index1];
        runners[index1] = runners[index2];
        runners[index2] = temp;
    }

    public static void main(String[] args) {
        Runner user1 = new Runner("홍길동", 5);
        Runner user2 = new Runner("임꺽정", 4);
        Runner user3 = new Runner("이순신", 3);
        Runner user4 = new Runner("나", 1);
        Runner user5 = new Runner("짱구", 5);

        Runner[] runners = {user1, user2, user3, user4, user5};

        System.out.println("===== 정렬 전 =====");
        System.out.println(Arrays.toString(runners));

        quickSortM(runners, 0, runners.length - 1);

        System.out.println("===== 정렬 후 =====");
        System.out.println(Arrays.toString(runners));
    }
}

결과

===== 정렬 전 =====
[{name: '홍길동', count: 5}, {name: '임꺽정', count: 4}, {name: '이순신', count: 3}, {name: '나', count: 1}, {name: '짱구', count: 5}]
===== 정렬 후 =====
[{name: '나', count: 1}, {name: '이순신', count: 3}, {name: '임꺽정', count: 4}, {name: '홍길동', count: 5}, {name: '짱구', count: 5}]

4. 두 번째 해결 - 가장 첫 번째 데이터인 여러분의 출석수를 변경

   1. 3번 코드에서 추가한 부분

      1. quickSortM()을 호출하고 모든 재귀 함수 호출이 끝난 시점인 if 가 필요

      2. Runner 클래스에서 setCount() 을 호출해서 변경

         1. 최소/최대 참여수는 불변값으로 변수 선언

   2. 문제점이 있다. 5번에서 해결하기

package sectionThree.quickSort.specialMission;

public class Runner {
    private String name;
    private int count;

    private static final int MIN_CHECK = 0; // 최소 참여수
    private static final int MAX_CHECK = 5; // 최대 참여수

    public Runner(String name, int count) {
        this.name = name;
        this.count = count;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        if (!(MIN_CHECK <= count && count <= MAX_CHECK)) return;
        this.count = count;
    }

    @Override
    public String toString() {
        return "{name: '" + name + "', count: " + count + '}';
    }
}

package sectionThree.quickSort.specialMission;

import java.util.Arrays;

public class QuickSortMission {
    public static void quickSortM(Runner[] runners, int left, int right) {
        if (left <= right) {
            int pivot = divideM(runners, left, right);

            quickSortM(runners, left, pivot - 1);
            quickSortM(runners, pivot + 1, right);
        }

        // 정렬이 다 끝난 후 - 가장 첫 번째 데이터인 '나'의 출석수를 변경
        if (right == runners.length - 1) {
            runners[0].setCount(5);
        }
    }

    public static int divideM(Runner[] runners, int left, int right) {
        int pivot = runners[left].getCount();
        int leftStartIndex = left + 1;
        int rightStartIndex = right;

        while (leftStartIndex <= rightStartIndex) {

            while (leftStartIndex <= right && pivot >= runners[leftStartIndex].getCount()) {
                leftStartIndex++;
            }

            while (rightStartIndex >= (left + 1) && pivot <= runners[rightStartIndex].getCount()) {
                rightStartIndex--;
            }

            if (leftStartIndex <= rightStartIndex) {
                swapM(runners, leftStartIndex, rightStartIndex);
            }
        }

        swapM(runners, left, rightStartIndex);
        return rightStartIndex;
    }

    public static void swapM(Runner[] runners, int index1, int index2) {
        Runner temp = runners[index1];
        runners[index1] = runners[index2];
        runners[index2] = temp;
    }

    public static void main(String[] args) {
        Runner user1 = new Runner("홍길동", 5);
        Runner user2 = new Runner("임꺽정", 4);
        Runner user3 = new Runner("이순신", 3);
        Runner user4 = new Runner("나", 1);
        Runner user5 = new Runner("짱구", 5);

        Runner[] runners = {user1, user2, user3, user4, user5};

        System.out.println("===== 정렬 전 =====");
        System.out.println(Arrays.toString(runners));

        quickSortM(runners, 0, runners.length - 1);

        System.out.println("===== 정렬 후 =====");
        System.out.println(Arrays.toString(runners));
    }
}

결과

===== 정렬 전 =====
[{name: '홍길동', count: 5}, {name: '임꺽정', count: 4}, {name: '이순신', count: 3}, {name: '나', count: 1}, {name: '짱구', count: 5}]
===== 정렬 후 =====
[{name: '나', count: 5}, {name: '이순신', count: 3}, {name: '임꺽정', count: 4}, {name: '홍길동', count: 5}, {name: '짱구', count: 5}]

5. 두 번째 해결 이어서 - 가장 첫 번째 데이터인 여러분의 출석수를 변경

   1. 현재 코드

      1. 결과는 예상 결과처럼 잘 나온다.

      2. 그런데 피벗을 기준으로 정렬할 때마다 Runner[] 첫 번째 배열의 count가 5로 변경된다.

      3. 정렬 도중에 여러 번 첫 번째 요소의 값을 변경할 가능성이 있어서 의도한 대로 동작하지 않을 수 있다.

   2. 내가 원했던 로직

      1. 모든 정렬이 끝난 후 Runner[] 첫 번째 배열의 count가 5로 변경된다.

      2. 해결 방법

         1. quickSortM() 함수 종료 후 main() 함수에서 runners[0].setCount(5); 진행 - 강사님 픽

         2. quickSortM() 에 depth 변수를 추가해서 정렬 후 0 depth인 경우에 runners[0].setCount(5); 를 진행

      3. 해결 방법 2번으로 진행해보자

package sectionThree.quickSort.specialMission;

import java.util.Arrays;

public class QuickSortMission {
    public static void quickSortM(Runner[] runners, int left, int right, int depth) {
        if (left <= right) {
            int pivot = divideM(runners, left, right);

            quickSortM(runners, left, pivot - 1, depth + 1);
            quickSortM(runners, pivot + 1, right, depth + 1);
        }

        if (depth == 0) {
            // 정렬이 다 끝난 후 - 가장 첫 번째 데이터인 '나'의 출석수를 변경
            runners[0].setCount(5);
        }
    }

    public static int divideM(Runner[] runners, int left, int right) {
        int pivot = runners[left].getCount();
        int leftStartIndex = left + 1;
        int rightStartIndex = right;

        while (leftStartIndex <= rightStartIndex) {

            while (leftStartIndex <= right && pivot >= runners[leftStartIndex].getCount()) {
                leftStartIndex++;
            }

            while (rightStartIndex >= (left + 1) && pivot <= runners[rightStartIndex].getCount()) {
                rightStartIndex--;
            }

            if (leftStartIndex <= rightStartIndex) {
                swapM(runners, leftStartIndex, rightStartIndex);
            }
        }

        swapM(runners, left, rightStartIndex);
        return rightStartIndex;
    }

    public static void swapM(Runner[] runners, int index1, int index2) {
        Runner temp = runners[index1];
        runners[index1] = runners[index2];
        runners[index2] = temp;
    }

    public static void main(String[] args) {
        Runner user1 = new Runner("홍길동", 5);
        Runner user2 = new Runner("임꺽정", 4);
        Runner user3 = new Runner("이순신", 3);
        Runner user4 = new Runner("나", 1);
        Runner user5 = new Runner("짱구", 5);

        Runner[] runners = {user1, user2, user3, user4, user5};

        System.out.println("===== 정렬 전 =====");
        System.out.println(Arrays.toString(runners));

        quickSortM(runners, 0, runners.length - 1, 0);

        System.out.println("===== 정렬 후 =====");
        System.out.println(Arrays.toString(runners));
    }
}

 결과

===== 정렬 전 =====
[{name: '홍길동', count: 5}, {name: '임꺽정', count: 4}, {name: '이순신', count: 3}, {name: '나', count: 1}, {name: '짱구', count: 5}]
===== 정렬 후 =====
[{name: '나', count: 5}, {name: '이순신', count: 3}, {name: '임꺽정', count: 4}, {name: '홍길동', count: 5}, {name: '짱구', count: 5}]