점수가 비슷한 학생들 끼리 조편성 알고리즘
1. 문제
학생들의 점수 목록이 배열로 주어진다. 그리고 k개 그룹으로 학생들을 묶을려고 합니다. 이때, 그룹별로 학생들의 점수 차이가 비슷 한 학생들 끼리 묶을려고 합니다. 그룹들의 점수가 가장 높은 친구의 점수와 가장 낮은 점수 차이들의 합이 최소값을 출력 하시오. 학생들의 점수 배열은 오름차순으로 정렬되어 입력 됩니다.
|
입력 점수 배열 |
입력 조 그룹 인원 |
출력 |
|
{1, 3, 7, 8, 10, 15} |
3 |
5 |
|
{1, 2, 12, 14, 15} |
2 |
4 |
2. 접근
1. 점수 목록 배열을 가지고 구간 별 차이를 구합니다.
2. 구간 차이가 작을수록 같은 그룹이 될 확률이 높습니다.
3. 구간 차이가 크면 다른 그룹으로 분리 시켜야할 기준이 됩니다.
3. 구간 차이 배열에서 값이 가장 큰 순서대로 k개를 뽑습니다.
4. k개의 값들을 그룹을 분리하기 위한 인덱스가 됩니다.
5. 따라서, 그룹의 최대값 - 최소값을 모두 더하여 반환 합니다.
3. java 1차 소스
import java.util.Arrays;
public class Second {
public static void main(String[] args) {
int[] ab = {1,3,7,8,10,15};
int k = 3;
int answer = 5;
// int[] ab = {1,2,12,14,15};
// int k = 2;
// int answer = 4;
Second second = new Second();
int a = second.solution(ab, k);
System.out.println(a);
}
public int solution(int[] scores, int k) {
int answer = 0;
// 구간 차 배열 구하기
int n = scores.length;
IntervalNode[] intervalDiffs = new IntervalNode[n - 1];
// O(N) = 300,000
for (int i = 0; i < n - 1; i++) {
int interval = scores[i + 1] - scores[i];
intervalDiffs[i] = new IntervalNode(interval, i);
}
// 구간차가 큰것부터 그룹화
// O(NlogN)
Arrays.sort(intervalDiffs);
// intervalDiffs 앞에서 부터 k 만큼 빼서 그룹을 만듬
List<Integer> scoresList = new ArrayList<Integer>(scores.length);
// O(N) = 300,000
for (int i : scores) {
scoresList.add(i);
}
// k - 1개 구간차가 큰값만 뽑기
int[] splitIndexs = new int[k - 1];
// O(N) = 300,000
for (int i = 0; i < k - 1; i++) {
splitIndexs[i] = intervalDiffs[i].index + 1;
}
// 인덱스 기준으로 정렬
// O(NlogN)
Arrays.sort(splitIndexs);
// intervalDiffs 앞에서 부터 k 만큼 빼서 그룹을 만듬
int beforeIdx = 0;
// O(N) = 300,000
for (int i = 0; i < splitIndexs.length; i++) {
int cutIdx = splitIndexs[i];
if (beforeIdx == cutIdx) { // 그룹의 1개의 원소가 존재할 경우
answer += 0;
} else {
// 이전 ~ cutIdx 까지
List<Integer> subList = scoresList.subList(beforeIdx, cutIdx);
// 그룹별 차이 구하기
answer += (subList.get(subList.size() - 1) - subList.get(0));
}
beforeIdx = cutIdx;
}
// 마지막 그룹의 sum += (가장 큰 - 가장 작은)
List<Integer> subList = scoresList.subList(beforeIdx, scoresList.size());
answer += (subList.get(subList.size() - 1) - subList.get(0));
return answer;
}
}
class IntervalNode implements Comparable<IntervalNode>{
int interval;
int index;
public IntervalNode(int interval, int index) {
this.interval = interval;
this.index = index;
}
@Override
public int compareTo(IntervalNode next) {
return next.interval - this.interval;
}
}IntervalNode 클래스는 interval, index 두개의 멤버변수를 가지가 있고, IntervalNode는 interval(구간 차)를 기준으로 내림 차순으로 정렬하고, index를 splitIndexs에게 반환 합니다. splitIndexes는 index를 기준으로 정렬하면서, k-1개의 index를 갖게 됩니다. splitIndexes를 기준으로 점수가 비슷한 학생달끼리 그룹핑을 할수 있습니다. 따라서, 그룹별 최고, 최점 점수 차를 모두 더하고, 반환 합니다.
4. java 2차 소스
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Second_2 {
public static void main(String[] args) {
int[] ab = {1,3,7,8,10,15};
int k = 3;
int answer = 5;
// int[] ab = {1,2,12,14,15};
// int k = 2;
// int answer = 4;
Second_2 second = new Second_2();
int a = second.solution(ab, k);
System.out.println(a);
}
public int solution(int[] scores, int k) {
// 구간 차 배열 구하여, 차이가 큰 인덱스를 k개 뽑아, 그룹핑 할수 있는 인덱스 배열을 만든다.
IndexesForSplitGetter indexesForSplitGetter = new IndexesForSplitGetter();
int[] indexesForSplit = indexesForSplitGetter.getIndexesForSplit(scores, k);
// 그룹핑할 인덱스 배열과 점수 배열을 가지고, 그룹별 점수 차이의 합을 반환 한다.
TotalGroupByScoresDiff totalGroupByScoresDiff = new TotalGroupByScoresDiff();
return totalGroupByScoresDiff.getTotal(indexesForSplit, scores);
}
}
class IndexesForSplitGetter {
public int[] getIndexesForSplit(int[] scores, int k) {
int n = scores.length;
ScoreIntervalDiffNode[] scoreIntervalDiffs = new ScoreIntervalDiffNode[n - 1];
// O(N) = 300,000
for (int i = 0; i < n - 1; i++) {
int interval = scores[i + 1] - scores[i];
scoreIntervalDiffs[i] = new ScoreIntervalDiffNode(interval, i);
}
// 구간차가 큰것부터 정렬
// in java
// Primitive Type의 Arrays.sort()는 Dual-Pivot-Quick-Sort => O(NlogN)
// 객체 Type의 Arrays.sort()는 TimSort => O(NlogN)
// 따라서, Tim Sort( Merge Sort + Insert Sort ) => O(NlogN)
Arrays.sort(scoreIntervalDiffs);
// k - 1개 구간차가 큰값만 뽑기
// O(N) = 300,000
int[] indexesForSplit = new int[k - 1];
for (int i = 0; i < k - 1; i++) {
indexesForSplit[i] = scoreIntervalDiffs[i].index;
}
// 인덱스 기준으로 정렬
// O(NlogN)
Arrays.sort(indexesForSplit);
return indexesForSplit;
}
}
class TotalGroupByScoresDiff {
public int getTotal(int[] indexesForSplit, int[] scores) {
int answer = 0;
// scoreIntervalDiffs 앞에서 부터 k 만큼 빼서 그룹을 만듬
// O(N) = 300,000
int beforeIdx = 0;
for (int i = 0; i < indexesForSplit.length; i++) {
int indexForSplit = indexesForSplit[i];
if (beforeIdx == indexForSplit) {
// 그룹의 1개의 원소가 존재할 경우
answer += 0;
} else {
// 이전 ~ indexForSplit 까지
// 그룹별 최저 점수, 최고 점수 차이 구하기
answer += (scores[indexForSplit] - scores[beforeIdx]);
}
beforeIdx = indexForSplit + 1;
}
// 마지막 그룹의 구가 차이 더하기
answer += (scores[scores.length - 1] - scores[beforeIdx]);
return answer;
}
}
class ScoreIntervalDiffNode implements Comparable<ScoreIntervalDiffNode>{
int interval;
int index;
public ScoreIntervalDiffNode(int interval, int index) {
this.interval = interval;
this.index = index;
}
@Override
public int compareTo(ScoreIntervalDiffNode next) {
return next.interval - this.interval;
}
}2차 소스에서는 네이밍을 일부 수정했습니다. IntervalNode를 좀더 구체화 시켜서 ScoreIntervalDiffNode로 변경 했습니다. 그리고 크게 두개의 클래스를 만들어 리팩토링을 진행 하였습니다. IndexesForSplitGetter 클래스는 구간 차를 구해서, 그룹핑 시킬 index 배열을 반환해 주는 역할을 합니다. TotalGroupByScoresDiff 클래스는 그룹핑 시킬 index 배열과 점수 배열을 받아서, 최고, 최저 점수 차의 합계를 반환 합니다. IndexesForSplitGetter.getIndexesForSplit()는 Arrays.sort()를 2번 사용하는데, Primitive Type의 Arrays.sort()는 Dual-Pivot-Quick-Sort => 시간 복잡도 : O(NlogN) 가 소요됩니다. 객체 Type의 Arrays.sort()는 Tim Sort( Merge Sort + Insert Sort ) => O(NlogN)를 보장 합니다. TotalGroupByScoresDiff. getTotal()은 1차 소스와 바뀐점이 int[] scores를 List<Integer> scoreList로 변환 하는 로직이 사라지고, list.subList를 통해서 그룹핑 하지 않고, 최고, 최저 점수의 차이만 알면 되므로, scores[]에서 바로 접근하여 차이값을 계산 합니다.
5. java 3차 소스
import java.util.PriorityQueue;
import java.util.Queue;
public class Second_3 {
public static void main(String[] args) {
int[] ab = {1,3,7,8,10,15};
int k = 3;
int answer = 5;
// int[] ab = {1,2,12,14,15};
// int k = 2;
// int answer = 4;
Second_3 second = new Second_3();
int a = second.solution(ab, k);
System.out.println(a);
}
public int solution(int[] scores, int k) {
// 구간 차 배열 구하여, 차이가 큰 인덱스를 k개 뽑아, 그룹핑 할수 있는 인덱스 배열을 만든다.
Integer[] indexesForSplit = IndexesForSplitGetter_3.getIndexesForSplit(scores, k);
// 그룹핑할 인덱스 배열과 점수 배열을 가지고, 그룹별 점수 차이의 합을 반환 한다.
return TotalGroupByScoresDiff_3.getTotal(indexesForSplit, scores);
}
}
class IndexesForSplitGetter_3 {
public static Integer[] getIndexesForSplit(int[] scores, int k) {
int n = scores.length;
Queue<ScoreIntervalDiffNode_3> scoreIntervalDiffQueue = new PriorityQueue(n - 1);
// interval(구간 차)가 큰 순서대로 구간차 큐를 만듬
for (int i = 0; i < n - 1; i++) {
int interval = scores[i + 1] - scores[i];
scoreIntervalDiffQueue.offer(new ScoreIntervalDiffNode_3(interval, i));
}
// k - 1개 구간차를 뽑는데 인덱스는 오름차순으로 정렬시켜 뽑기
Queue<Integer> indexesForSplitQueue = new PriorityQueue<>(k - 1);
for (int i = 0; i < k - 1; i++) {
ScoreIntervalDiffNode_3 node = scoreIntervalDiffQueue.poll();
if (node != null) {
indexesForSplitQueue.offer(node.getIndex());
}
}
return indexesForSplitQueue.toArray(new Integer[k - 1]);
}
}
class TotalGroupByScoresDiff_3 {
public static int getTotal(Integer[] indexesForSplit, int[] scores) {
int answer = 0;
// scoreIntervalDiffs 앞에서 부터 k 만큼 빼서 그룹을 만듬
// O(N) = 300,000
int beforeIdx = 0;
for (int i = 0; i < indexesForSplit.length; i++) {
int indexForSplit = indexesForSplit[i];
if (beforeIdx == indexForSplit) {
// 그룹의 1개의 원소가 존재할 경우
answer += 0;
} else {
// 이전 ~ indexForSplit 까지
// 그룹별 최저 점수, 최고 점수 차이 구하기
answer += (scores[indexForSplit] - scores[beforeIdx]);
}
beforeIdx = indexForSplit + 1;
}
// 마지막 그룹의 구가 차이 더하기
answer += (scores[scores.length - 1] - scores[beforeIdx]);
return answer;
}
}
class ScoreIntervalDiffNode_3 implements Comparable<ScoreIntervalDiffNode_3>{
private int interval;
private int index;
public ScoreIntervalDiffNode_3(int interval, int index) {
this.interval = interval;
this.index = index;
}
public void setIndex(int index) {
this.index = index;
}
public int getIndex() {
return index;
}
public void setInterval(int interval) {
this.interval = interval;
}
public int getInterval() {
return interval;
}
@Override
public int compareTo(ScoreIntervalDiffNode_3 next) {
return next.interval - this.interval;
}
}3차 소스 코드는 바뀐 부분이 static(정적) 메서드로 변경 하였습니다. ScoreIntervalDiffNode과 같이 도메인과 비즈니스 로직과 연관된 부분이 많아서 static 메서드로 바꾸지 않는것이 더 좋지만, 보기 편하게 하기 위해서 static으로 바꾸어 주었습니다. 그리고, IndexesForSplitGetter_3.getIndexesForSplit() 이 메서드는 Arrays.sort()가 2번 들어가는데, 이 부분을 자료구조를 활용하여 줄이고 싶었습니다. 그렇게 하기 위해서는 삽입시의 원소들이 정렬 되는 자료구조를 선택해야 합니다. 삽입시 정렬을 지원하는 자료구조는 Tree구조를 이용한 TreeMap, TreeSet이 있습니다. java에서는 Tree를 레드-블랙 트리로 구현하여 삽입시 정렬된 상태를 유지 합니다. 하지만, Set의 경우 중복을 허용하지 않고, Map의 경우도 key값은 중복을 혀용하지 않습니다. 그래서 PriorityQueue를 사용 했습니다. scoreIntervalDiffQueue를 정의하여, interval 기준으로 정렬 하여 삽입 하고, indexesForSplitQueue를 정의하여, index를 기준으로 정렬하여 삽입하여, Integer[]로 반환 시켜 줍니다.