[다중조건정렬/Comparator] 41. 다중조건정렬

1. Problem

[학점] double[] score = [4.5, 3.1, 2.0, 3.9, 3.8]

[학교와의 거리] int[][] home = [[2,1] ,[-4,4] ,[3,7] ,[1,2] ,[4,4]]

[이름] String[] name = ["andrew", "boyeon", "hojoon", "dayung", "danbie"]

 

학생들의 기숙사 우선순위를 구하는 문제이다.

학점 , 거리, 이름 순으로 순으로 우선순위가 결정된다.

학점은 앞자리만 비교한다.

예를 들어 4.5와 4.1은 같은 4이기때문에 학교와의 거리로 우선순위를 결정한다.

거리도 같다면 이름 순으로 우선순위가 결정된다.

학교의 좌표는 [0,0]이다.

 

예제 설명)

학점 4, 3, 2, 3, 3

→ 학점 우선순위가 같은 2,4,5번째 학생을 거리에서 비교

학교와의거리 2번째학생: 32, 4번째 학생: 5, 5번째 학생: 32

→ 2,5번째 학생이 4번째 학생보다 멀기 때문에 우선순위가 높고 두 학생의 거리 같으므로 이름을 비교한다.

이름 2번째 학생이 5번째 학생보다 우선순위이므로 정답은 1, 2, 5, 4, 3이다.

 

정답: [1,2,5,4,3]

 

 

2. Code

 

1) 처음풀이

package SKCNC;

import java.util.Arrays;

public class ex2 {

	public static void main(String[] args) {
		double[] score = {4.5, 3.1, 2.0, 3.9, 3.8};
		int[][] home = {{2,1},{-4,4},{3,7},{1,2},{4,4}};
		String[] name = {"andrew", "boyeon", "hojoon", "dosoeung", "eanbie"};
		
		solution(score, home, name);
	}
	
	public static int[] solution(double[] score, int[][] home, String[] name) {
		int[] answer = new int[score.length];
		int start = 0;
		while(start < score.length) {
			for(int i = 0; i < score.length; i++) {
				if((int)score[start] < (int)score[i]) answer[start]++;
			}
			start++;
		}
		
		for(int i = 0; i < answer.length; i++) {
			System.out.print(answer[i]+ " ");
		}
		System.out.println();
		
		start = 0;
		while(start < home.length) {
			for(int i = 0; i < home.length; i++) {
				if(i != start && answer[start] == answer[i]) {
					int startDis = (int) (Math.pow(home[start][0], 2)+ Math.pow(home[start][1], 2));
					int iDis = (int) (Math.pow(home[i][0], 2)+ Math.pow(home[i][1], 2)); 
					if(startDis > iDis) {
						answer[start]++;
					} else if(startDis < iDis) {
						answer[i]++;
					}
				}
			}
			start++;
		}
		
		for(int i = 0; i < answer.length; i++) {
			System.out.print(answer[i]+ " ");
		}
		System.out.println();
		
		start = 0;
		while(start < name.length) {
			for(int i = 0; i < name.length; i++) {
				if(start != i && answer[start] == answer[i]) {
					String[] str = {name[start], name[i]};
					Arrays.sort(str);
					if(str[0].equals(name[start])) answer[i]++;
					else answer[start]++;
				}
			}
			start++;
		}
		
		for(int i = 0; i < answer.length; i++) {
			System.out.print(answer[i]+ " ");
		}
		return answer;
	}
	
	
	

}

 

2) Collection.sort과 comparator 이용

package SKCNC;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ex2Another {

	public static void main(String[] args) {
		double[] score = {4.5, 3.1, 2.0, 3.9, 3.8};
		int[][] home = {{2,1},{-4,4},{3,7},{1,2},{4,4}};
		String[] name = {"andrew", "boyeon", "hojoon", "dosoeung", "eanbie"};
		solution(score, home, name);
	}
	
	public static int[] solution(double[] score, int[][] home, String[] name) {
		int[] answer = new int[score.length];
		List<Student> studList = new ArrayList<>();
		for(int i = 0; i < score.length; i++) {
			Student student = new Student(i+1, (int) score[i], home[i][0]*home[i][0] + home[i][1]*home[i][1], name[i]);
			studList.add(student);
		}
		
		Collections.sort(studList, new Comparator<Student>() {
			public int compare(Student s1, Student s2) {
				if(s1.score < s2.score) return 1;
				else if(s1.score > s2.score) return -1;
				else {
					if(s1.distance < s2.distance) return 1;
					else if(s1.distance > s2.distance) return -1;
					else {
						return s1.name.compareTo(s2.name);
					}
				}
			}
		});
		
		for(int i = 0; i < studList.size(); i++) {
			Student student = studList.get(i);
			answer[i] = student.getIdx();
		}
		
		return answer;
	}
	
	public static class Student {
		private int idx;
		private int score;
		private int distance;
		private String name;
		
		public Student() {}
		
		public Student(int idx, int score, int distance, String name) {
			this.idx = idx;
			this.score = score;
			this.distance = distance;
			this.name = name;
		}
		
		public int getScore() {
			return score;
		}
		public int getDistance() {
			return distance;
		}
		public String getName() {
			return name;
		}
		public int getIdx() {
			return idx;
		}
	}

}

 

3) 우선순위큐와 comparator 이용

package SKCNC;

import java.util.Comparator;
import java.util.PriorityQueue;

import SKCNC.ex2Another.Student;

public class ex2Last {

	public static void main(String[] args) {
		double[] score = {4.5, 3.1, 2.0, 3.9, 3.8};
		int[][] home = {{2,1},{-4,4},{3,7},{1,2},{4,4}};
		String[] name = {"andrew", "boyeon", "hojoon", "dosoeung", "eanbie"};
		solution(score, home, name);

	}
	public static int[] solution(double[] score, int[][] home, String[] name) {
		int[] answer = new int[score.length];
		PriorityQueue<Student> heap = new PriorityQueue<>(new Comparator<Student>() {
				@Override
				public int compare(Student s1, Student s2) {
					if(s1.score < s2.score) return 1;
					else if(s1.score > s2.score) return -1;
					else {
						if(s1.distance < s2.distance) return 1;
						else if(s1.distance > s2.distance) return -1;
						else {
							return s1.name.compareTo(s2.name);
						}
					}
				}
		});
		
		for(int i = 0; i < score.length; i++) {
			Student std = new Student(i+1, (int) score[i], home[i][0]*home[i][0] + home[i][1]*home[i][1], name[i]);
			heap.add(std);
		}
		
		for(int i = 0; i < answer.length; i++) {
			answer[i] = heap.poll().getIdx();
			System.out.print(answer[i] + " ");
		}
		
		return answer;
	}
	
	
	
	public static class Student {
		private int idx;
		private int score;
		private int distance;
		private String name;
		
		public Student() {}
		
		public Student(int idx, int score, int distance, String name) {
			this.idx = idx;
			this.score = score;
			this.distance = distance;
			this.name = name;
		}

		public int getIdx() {
			return idx;
		}
		
		public int getScore() {
			return score;
		}
		
		public int getDistance() {
			return distance;
		}
		
		public String getName() {
			return name;
		}
		
	}

}

3. report

다중조건정렬을 처음 풀어봤다 ㅠㅠ..

Comparator로 풀기 전에 풀이는 정말 효율성이 제로다 제로..

객체 만들어서 Collection.sort를 이용하여 Comparator을 내가 설정해서 풀 수 있었다.

마지막으로는 리스트에 넣어놓고 정렬하는게 아니라

우선순위큐 조건 자체를 comparator 를 이용해서 넣는 순간 정렬되게 만들었다.