[워밍업 클럽 3기 CS 전공지식] 자료구조와 알고리즘 특별 미션
문제실수로 워밍업 클럽 출석을 빼먹었는데 우연히 데이터를 수정할 수 있는 권한이 주어졌습니다. 러너분의 이름(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로 작성]이전에 작성한 퀵소트 정렬 코드 참고하기다른 점숫자 배열이 아닌 객체 배열을 만들어야 한다.객체 배열 안에서 count 로 오름차순을 한다.첫 번째 해결 - count로 오름차순하기name과 count를 함께 저장할 수 있는 Runner 클래스 생성이전 코드에서 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}] 두 번째 해결 - 가장 첫 번째 데이터인 여러분의 출석수를 변경3번 코드에서 추가한 부분quickSortM()을 호출하고 모든 재귀 함수 호출이 끝난 시점인 if 가 필요Runner 클래스에서 setCount() 을 호출해서 변경최소/최대 참여수는 불변값으로 변수 선언문제점이 있다. 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}] 두 번째 해결 이어서 - 가장 첫 번째 데이터인 여러분의 출석수를 변경현재 코드결과는 예상 결과처럼 잘 나온다.그런데 피벗을 기준으로 정렬할 때마다 Runner[] 첫 번째 배열의 count가 5로 변경된다.정렬 도중에 여러 번 첫 번째 요소의 값을 변경할 가능성이 있어서 의도한 대로 동작하지 않을 수 있다.내가 원했던 로직모든 정렬이 끝난 후 Runner[] 첫 번째 배열의 count가 5로 변경된다.해결 방법quickSortM() 함수 종료 후 main() 함수에서 runners[0].setCount(5); 진행 - 강사님 픽quickSortM() 에 depth 변수를 추가해서 정렬 후 0 depth인 경우에 runners[0].setCount(5); 를 진행해결 방법 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}]
