Comparator
저번에 공부하였던 정렬 내용 중 추가적으로 공부할 내용이 있어서 정렬에 대한 부분을 더 적어봅니다.
정렬에서 배웠던 Object[] Sort 중 내림차순으로 정렬하는 방법입니다.
기본 예시 코드를 봐봅시다!
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
}
}
위의 코드를 보면 Object[] sort는 Comparator를 추가로 전달할 수 있습니다. 아래 이미지는 Java에 적혀있는 Comparator대한 내용입니다.
일부분을 이야기하자면 Comparator는 함수형 인터페이스로 두 개의 문자열을 받아서 그 순서를 비교합니다. o1과 o2를 받았을 때 Return 해주는 값은 o1이 더 적다면 음수를, o1과 o2가 같다면 0을, o1이 더 크다면 양수를 Return합니다.
그래서 정렬 알고리즘이 순서를 정할 때 사용하는 부분이 Comparator입니다.
한 번 코드로 보겠습니다.
Integer[] objectArray = {6, 2, 3, 7, 5, 1, 4};
// Arrays.sort(objectArray, Collections.reverseOrder()); // 기존 코드
Arrays.sort(objectArray, new Comparator<Integer>() {
@Override
public int compare(Intger o1, Integer o2) {
return o2 - o1; // 내림차순
// 만약 오름차순으로 정렬하고 싶다면?
// return o1 - p2;
}
}
for (Integer x : objectArray)
System.out.println(x);
즉, 두 원소를 비교했을 때 o1이 o2보다 먼저 나오려면 return 음수, o2가 먼저 나오려면 return 양수, 원본에서 순서대로 나오려면 return 0(stable)이 된다.
Lambda
Comparator가 잠깐 사용되는 임시 객체이고 compare이라는 추상 메서드 하나만 가진 함수형 인터페이스이어서 Lambda로 변형이 가능합니다.
아래 이미지를 보면 Replace wit lambda가 나옵니다.
Arrays.sort(objectArray, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; // 내림차순
// 만약 오름차순으로 정렬하고 싶다면?
// return o1 - p2;
}
}
// 위의 코드를 아래 코드로 변형이 가능하다.
Arrays.sort(objectArray, (o1, o2) -> { return o2 - o1; }
Custom Class
기본 제공되는 type이 아닌 내가 직접 정의한 클래스로 정렬을 하고 싶다면 어떻게 해야할까요?
정렬하기 위해서는 두 원소를 비교해야 하는데 새로 정의된 Student Class의 정렬 기준은 알 수 없습니다..
public static class Student {
String name;
int age;
Student(String name, int age) {
this.name = name;
this.age = age;
}
}
public static void main(String[] args) {
Integer[] objectArray = {6, 2, 3, 7, 5, 1, 4};
Student[] studets = {new Student("Bulmange", 25), new Student("Flutter", 24), new Student("iOS", 23)};
Arrays.sort(studets);
for (Student x : studets) {
System.out.println(x.name + " " +x.age);
}
}
위의 코드를 보면 이해가 됩니다.
직접 Student class를 만들고 그것을 정렬하여 출력하는 코드를 작성했습니다.
실행하면 어떻게 될 것 같나요? 바로 런타임 에러가 발생합니다.
“ Student Class가 Comparable type으로 casting 할 수 없다. “ 문구가 나옵니다.
그 이유는 정렬을 하기 위해서는 두 원소를 비교해야 하는데 새로 정의된 Student class의 정렬 기준을 알 수 없기 때문입니다.
그러면 Comprable하게 만들면 된다.
1. Comparable Intferface 구현
Student class를 Comparable를 implements하고 compareTo Override를 하면 된다.
이러면 정렬 기준이 생기고 아래처럼 나이와 이름을 정렬할 수 있게 된다.
public static class Student implements Comparable<Student> {
String name;
int age;
Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Student o) {
if (this.age == o.age) // 나이가 같다면
return this.name.compareTo(o.name); // 이름에 대한 사전순 정렬
return this.age - o.age ;
}
}
2. Comparator 사용
아니면 Comparator를 사용하여 Student class는 그대로 놔두고 Arrays.sort에 코드를 더하면 된다.
이렇게 하면 두 원소를 입력받아 비교를 한다. 비교 기준이 생긴다.
public static void main(String[] args) {
Integer[] objectArray = {6, 2, 3, 7, 5, 1, 4};
Student[] studets = {new Student("Bulmange", 25), new Student("Java", 25), new Student("Flutter", 24), new Student("iOS", 23)};
Arrays.sort(studets, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if (o1.age == o2.age)
return o1.name .compareTo(o2.name);
return o1.age - o2.age;
}
});
for (Student x : studets) {
System.out.println(x.name + " " +x.age);
}
}
어떨 때 1번과 2번을 사용할 것 인가?
이것은 개발자의 취향 차이 부분이긴 한다.
하지만 나는 정렬을 1회용으로 사용한다 하면 Comparator를 사용하여 정렬을 하고
만약 재사용을 한다거나 정렬 기준이 중요하다면 Comparable를 implements하여 사용한다.
[7785] 회사에 있는 사람
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 66890 | 27885 | 21169 | 40.847% |
문제
상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.
출력
현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.
문제 풀이
문제는 회사 출입기록이 있을 때, 아직 퇴근하지 못한 사람의 목록을 사전 역순으로 출력하면 된다.
이 때 주의해야 할 점은 퇴근한 사람이 다시 들어올 수 있다는 점이다.
처음 문제를 풀려고 하였던 방식은 회사에 있는 사람 목록을 관리하여 반복문과 Sort를 해주려고 했다.
그래서 아래 코드를 작성하였는데 시간복잡도가 O(n^2)이 나오게 되어 다른 문제 풀이 방식으로 풀었다.
String[] inCompanyList = new String[N];
int inCompanyListLength = 0;
for (int i=0; i<N; i++) {
String name = sc.next();
String status = sc.next();
if (status.equals("enter")) {
// append name to list
inCompanyList[inCompanyListLength++] = name;
} else {
// delete name from list
// 아래 코드가 최악의 경우 N/2의 값이 들어오고 N/2 값이 나가게 되면 시간초과를 받게 된다.
for(int j=0; j<inCompanyListLength; j++)
if(inCompanyList[j].equals(name)) {
inCompanyList[j] = "";
break;
}
}
}
그러면 각 사원의 기록을 차례로 봤을 때, 마지막 기록이 아직 enter라면 회사에 남아있는 것으로 보면 된다.
아래 정렬을 사용하면 같은 사원에 대한 기록을 묶어서 차례로 모이게 할 수 있다.
1. 이름 순서에 따라 출입기록을 차례로 정렬한다.
출퇴근 기록은 “enter” 혹은 “leave”로 총 두개이니 두개의 크기를 잡고 이름은 N개의 배열 크기로 잡아준다.
그리고 나서 Comparator를 사용하여 역순으로 출력해야하니 역순으로 정렬하여 저장한다.
String[][] records = new String[N][2];
for(int i=0; i<N; i++) {
records[i][0] = sc.next();
records[i][1] = sc.next();
}
Arrays.sort(records, new Comparator<String[]>() {
@Override
public int comapre(String[] o1, String[] o2) {
return o2[0].compareTo(o1[0]);
}
});
2. 각 사원마다 마지막 기록이 enter인지 확인한다.
아래 코드를 보게 되면 조건이 2개 이다.
1번 조건 records[i][1]이 “enter”이어야 한다.
2번 조건 records[i][0]이 records[i+1][0]과 달라야한다. 이게 무슨말이냐면 사원끼리 묶어서 정렬했는데 이름이 다르다면 그사람의 마지막 기록이라는 것. 즉 그 이후 새로 업데이트되는 조건이 없다는 것이다.
2-1. 마지막 기록이 enter라면 출력한다.
그래서 반복문을 N-1까지 하는데 이것은 N-2까지 반복하여 계산을 하는 것이고 그래서 if문을 추가하는 것도 마지막 요소를 계산하기 위해서 작성하는 것이다.
for (int i=0; i<N-1; i++) {
if(records[i][1].equals("enter") && !records[i][0].equals(records[i+1][0]))
System.out.println(records[i][0]);
}
// 마지막 기록이 enter라면 출력
if (records[N-1][1].equals("enter"))
System.out.println(records[N-1][0]);
시간복잡도
이 알고리즘의 시간복잡도는 입력받는 과정이 O(N)이고 정렬하는 과정에서 O(NlogN)이다.
출력할때도 O(N)이 나온다. 즉, O(NlogN)이다
전체코드
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// 1. 일름 순서에 따라 출입기록을 차례로 정렬
String[][] records = new String[N][2];
for(int i=0; i<N; i++) {
records[i][0] = sc.next();
records[i][1] = sc.next();
}
Arrays.sort(records, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
return o2[0].compareTo(o1[0]);
}
});
// 2, 각 사원마다 마지막 기록이 enter라면 사전의 역순으로 출력한다
for(int i=0; i<N-1; i++) {
if(records[i][1].equals("enter") && !records[i][0].equals(records[i+1][0]))
System.out.println(records[i][0]);
}
if(records[N-1][1].equals("enter"))
System.out.println(records[N-1][0]);
}
}
새로운 문제풀이
회사에 있는 사람 목록을 관리하여 푸는 방법도 있다.
아까 시간이 초과하여 못 풀었떤 방식을 삽입/삭제 연산이 빠른 집합 자료구조로 푼다면 된다.
java.util.Set
Set은 중복된 원소를 가지지 않는 Collection이다.
아래 코드는 Set class에 특성에 대해서 알아 볼 수 있는 코드이다.
add, remove, contains의 시간복잡도는 O(1)~O(비교복잡도 * log(size))이다
Set<String> set = new HashSet();
set.add("C");
set.add("B");
set.add("B"); // 이미 존재한다면 추가가 되지 않음. 중복 제거
set.remove("A"); // 존재하지 않는다면 수행되지 않음.
set.contains("B"); // B가 있다면 true, 없다면 false 반환
set.size(); // 길이를 반환함.
Set의 종류
위에 코드에 있는 Set은 HashSet을 따르고 있다.
Set은 interface라서 구현체를 알아야 한 다. 구현체 중 가장 자주 사용되는 부분은 HashSet과 TreeSet이다.
아래 이미지를 보며 차이점을 비교해 보자.
HashSet은 해시 테이블을 기반으로 a, b, c, d 문자열이 있으면 한번에 비교하는 값으로 변환한다. 그리고 저장되는 값은 순서가 없이 저장이 된다. 항상 O(1)이 아니이고 충돌 가능성도 있다.
TreeSet은 BinarySearchTree를 기반으로 한다 Set에 저장되는 원소들이 순서를 갖는다. sort처럼
Integer는 오름차순 정렬, String은 사전순 정렬
Set을 사용해서 변경
TreeSet를 이용하여 역순으로 출력하는 방법이다.
전체 시간 복잡도는 처음 원소를 삽입할때 비교를 해서 정렬해서 가지고 있다. O(N) 삽입할때 O(logN)이고 삭제할때 O(logN)이 된다.
그래서 전체 시간복잡도: O(N * LlogN)이다.
확실히 Set을 사용하게되니 더욱 코드가 간단하게 출력이 된다.
import java.util.*;
class Main {
public static void main(String[] args) {
// 1. TreeSet을 사용하여 일름 순서에 따라 출입기록을 차례로 정렬
Set<String> entered = new TreeSet<>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for(int i=0; i<N; i++) {
String name = sc.next();
String status = sc.next();
// 2. enter라면 add, enter가 아니라면 remove를 해주어 enter를 가진 사람만 존재한다.
if (status.equals("enter"))
entered.add(name);
else entered.remove(name);
}
// 3. 역순으로 정렬하여 출력하기.
String[] orderedAnswer = entered.toArray(new String[entered.size()]);
for (int i=orderedAnswer.length-1; i>=0; i--)
System.out.println(orderedAnswer[i]);
}
}
[1302] 베스트셀러
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 2 초 | 128 MB | 29128 | 15822 | 13130 | 54.518% |
문제
김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.
오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.
출력
첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.
문제풀이
이 문제는 가장 많이 팔린 책의 제목을 출력하면 된다.
1. 데이터를 묶기 위해 Book 클래스 생성
일단 데이터를 이름과 개수를 저장하기 위해서 book이라는 클래스를 만들어주었습니다.
만들어 질 때 개수가 1개 생기는 것이니 초기값을 1로 지정했습니다.
public static class Book {
String name;
int count;
Book(String name) {
this.name = name;
this.count = 1;
}
}
2. 책 추가
그렇게 책을 추가할때 boolean found 변수를 이용하여 중복을 구했습니다.
만약 책 제목이 현재 저장되어있는 책 중 제목과 같다면 개수를 증가시키고 found를 true로 하였습니다.
만약 found가 없다면 새로운 Book을 넣어줬습니다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Book[] books = new Book[N];
int bookCount = 0; // 실제 저장된 책 수
for (int i = 0; i < N; i++) {
String bookName = sc.next();
boolean found = false;
// 중복된 책 제목 확인
for (int j = 0; j < bookCount; j++) {
if (books[j].name.equals(bookName)) {
books[j].count++; // 카운트 증가
found = true;
break;
}
}
// 새로운 책 추가
if (!found) {
books[bookCount++] = new Book(bookName); // 새로운 Book 객체 생성
}
}
3. 가장 많이 팔린 책 찾기
3.1 개수가 같다면 사전순으로 비교
가장 많이 팔린 책을 찾기 위해서 maxCount를 생성해주어 하나씩 비교를 하고 0보다 크다면 maxCount로 바꾸어주고 또 비교를 하여 제일 개수가 많은 책이 들어가게 했습니다. 그리고 개수가 같다면 compareTo를 사용하여 음수로 만들어주어 사전순으로 출력하게 만들었습니다.
// 가장 많이 팔린 책 찾기
String mostSoldBook = "";
int maxCount = 0;
for (int i = 0; i < bookCount; i++) {
if (books[i].count > maxCount) {
maxCount = books[i].count;
mostSoldBook = books[i].name;
} else if (books[i].count == maxCount) {
// 카운트가 같으면 사전순으로 비교
if (books[i].name.compareTo(mostSoldBook) < 0) {
mostSoldBook = books[i].name;
}
}
}
시간복잡도
이 알고리즘의 시간복잡도는 입력할때 O(N), 중복비교할때O(N^2) 즉 O(N^2)이다.
좋지 않은 시간복잡도이다.
두 번째 풀이
Arrays.sort를 이용하여 풀어보겠다.
0. 예제 입력
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String[] titles = new String[N];
for (int i=0; i<N; i++) {
titles[i] = sc.next();
}
1. 일단 마찬가지로 팔린 책의 개수를 비교하자
titles를 정렬하면 같은 책들이 정렬될테니 앞뒤로 비교할 수 있다.
2. 만약 같다면 사전순으로 출력하면 된다.
만약 i번째와 i-1번째의 책이름이 같다면 현재 개수를 1증가 시키고 아니면 0으로 설정
그래서 maxCount가 더 작거나 같다면 사전순으로 정렬하여 maxCount와 maxTitle에 값을 넣어준다.
Arrays.sort(titles);
String maxTitle = titles[0];
int maxCount =1;
int currentCount = 1;
for(int i=1; i<N; i++) {
if (!titles[i].equals(titles[i-1]))
currentCount = 0;
currentCount++;
if (maxCount < currentCount || (maxCount == currentCount && titles[i].compareTo(maxTitle) < 0)) {
maxCount = currentCount;
maxTitle = titles[i];
}
}
System.out.println(maxTitle);
시간복잡도
이 알고리즘의 시간복잡도는 Arrays.sort를 할 때 NlogN * L 이 나온다
즉, O(L*NlogN)이다.
Map을 사용한 문제풀이
Map은 중복된 Key를 가지지 않고, [key]: value 쌍을 담는 Collection이다.
put, remove, containsKey 메서드들의 시간복잡도는 O(1) ~ O(비교복잡도 * log(size))이다.
Map<String, Integer> map = new HashMap<>();
map.put("Bulmang", 25);
map.put("iOS", 23);
map.put("Flutter", 24);
System.out.println(map.size()); // 3
map.remove("Bulmang")
map.remove("Bulmang") // 원소가 없으므로 삭제 수행되지 않음
map.containsKey("Bulmang") // false
map.containsKey("iOS") // true
Map의 구현체를 봐보자. Map 역시 마찬가지로 interface이다.
HashMap과 TreeMap이 있다.
아래 특징을 보며 둘의 차이를 비교해보자, Set과 비슷한 것을 확인할 수 있는데 Set 자료구조는 내부적으로 Map자료구조를 불러서 구현체로 사용하고 있다.
// 1. HashMap titles 생성
Map<String, Integer> titles = new HashMap<>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for(int i=0; i<N; i++) {
String title = sc.next();
titles.put(title, titles.getOrDefault(title, 0)+1);
}
// 2. 조건에 맞는 값 찾기
int maxCount = 0;
String maxTitle = "";
for(Map.Entry<String, Integer> title : titles.entrySet()) {
String titleName = title.getKey();
int count = title.getValue();
if(maxCount < count || (maxCount == count && titleName.compareTo(maxTitle)<0)) {
maxTitle = titleName;
maxCount = count;
}
}
System.out.println(maxTitle);
사실 위처럼 HashMap을 사용할 경우에는 정렬이 되지 않기 때문에 compareTo메서드를 사용해야 하지만 나는
TreeMap을 사용해서 조건 줄여보겠다.
아래 코드 같은경우 이미 정렬이 되어 있기 때문에 개수가 같을때 사전정렬을 할 필요가 없다.
import java.util.*;
class Main {
public static void main(String[] args) {
Map<String, Integer> titles = new TreeMap<>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for(int i=0; i<N; i++) {
String title = sc.next();
titles.put(title, titles.getOrDefault(title, 0)+1);
}
int maxCount = 0;
String maxTitle = "";
for(Map.Entry<String, Integer> title : titles.entrySet()) {
String titleName = title.getKey();
int count = title.getValue();
if(maxCount < count ) {
maxTitle = titleName;
maxCount = count;
}
}
System.out.println(maxTitle);
}
}
이렇게 HashMap과 TreeMap을 사용해서 풀어보았다.
정렬로도 풀어야 할 줄 알고 또 Map과 Set을 이용하여 풀어보기도 하며 여러 방법으로 문제를 푸는 습관을 길러보자.
시간복잡도
이 알고리즘의 시간복잡도는 **O(L * NlogN)**이다.
'알고리즘 > Sort' 카테고리의 다른 글
| [코딩테스트] [1931] 회의실 배정 (2) | 2024.12.11 |
|---|---|
| [코딩테스트] [18870] 좌표 압축 & [2910] 빈도 정렬 (0) | 2024.12.10 |
| [코딩테스트] 정렬(Sort) & [2751] 수 정렬하기 2 & [1181] 단어정렬 & [10841] 나이순 정렬 (0) | 2024.12.06 |