백준 30970번 : 선택의 기로 (Comparator 구현)
품질이냐 가격이냐, 그것이 문제로다…
이번 문제는 “촉석루”라는 특이한 주제가 있지만, 사실 이 주제는 아무거나 대입해도 괜찮다.
주된 내용은 미니어처를 구입하기 위해 고민하는 내용인데, 이 구입하는 방법에 대한 두 가지 방법이 있다.
첫 번째 방법은 미니어처 중 품질이 가장 높은 미니어처를 고르고, 동일한 품질에 대해 가격이 가장 낮은 것을 고른다.
두 번째 방법은 미니어처 중 가격이 가장 낮은 미니어처를 고르고, 동일한 가격에 대해 품질이 가장 높은 것을 고른다.
이 두 가지 방법을 실행하여 각각 미니어처를 두 개 구입할 때의 경우, 미니어처의 품질과 가격을 리턴하는 문제이다.
즉, 한 가지 방법에 두 개씩 결과가 리턴되어야 한다.
입력과 출력을 살펴보면
입력
1
2
3
4
5
4
3 1
2 2
2 3
1 1
출력
1
2
3 1 2 2
3 1 1 1
이렇게 되어 있다.
입력 시 최초에 미니어처의 개수인 n이 입력되고 이후로 품질 가격이 연달아 리턴된다.
출력은 각 방법을 거친 미니어처 2개의 품질과 가격을 공백으로 구분해서 출력한다.
우선 정렬 방법이 두 가지로 나뉘어 있기 때문에 클래스를 활용하던 메인 함수에서 처리하던 정렬을 직접 구현해야 한다.
만약 조건이 한 가지이고, 각 개체의 값이 두 가지였다면 클래스를 활용하여 Comparable 인터페이스를 구현해서 정렬 처리했을테지만,
조건이 두 가지이기 때문에 “촉석루”라는 객체를 구현하고, 이너 클래스를 활용하여 Comparator 인터페이스를 구현했다.
혹은 메인 함수 내부에서 Collections를 활용하여 구현해도 된다.
하지만 클래스로 분리해서 구현하는 것이 보기에도 명확한 것 같아서 정렬 인터페이스를 구현한 클래스들을 활용한 것이다.
우선 촉석루 객체를 구현하여 각 품질과 가격에 대한 값을 저장해야한다.
1
2
3
4
5
6
7
8
9
class Chock {
int quality;
int price;
public Chock(int quality, int price) {
this.quality = quality;
this.price = price;
}
}
이 객체를 활용하여 입력된 데이터에 대해 핸들링할 것이다.
이러한 클래스를 활용하는 방법이 문제를 해결하는 데에 있어서 가독성도 좋고 불필요한 자료구조를 복잡하게 활용하지 않아도 된다.
다음으로는 “두 가지 정렬 방법”에 대한 이너 클래스를 생성해서 Comparator 인터페이스를 구현한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 첫 번째 방법 : 품질 우선 정렬, 동일하면 가격이 낮은 순
static class QualityComp implements Comparator<Chock> {
public int compare(Chock c1, Chock c2) {
if (c1.quality == c2.quality) {
return c1.price - c2.price;
}
return c2.quality - c1.quality;
}
}
// 두 번째 방법 : 가격 우선 정렬, 동일하면 품질이 높은 순
static class PriceComp implements Comparator<Chock> {
public int compare(Chock c1, Chock c2) {
if (c1.price == c2.price) {
return c2.quality - c1.quality;
}
return c1.price - c2.price;
}
}
Comparator 는 객체를 비교하기 위한 인터페이스이다.
기존에 몇 번 사용했던 Comparable의 경우 “자기 자신과 매개변수 객체를 비교”하는 것이고, 이번에 활용하는 Comparator의 경우 “두 매개변수 객체를 비교”하는 인터페이스이다.
여기서 Comparable의 경우 compareTo() 함수를 구현해야하는데, 이 함수는 한 클래스에 대해 한 가지 정렬 기준만 설정할 수 있다.
하지만 Comparator의 경우 여러 개의 별도 정렬을 정의할 수 있기 때문에 두 가지 서로 다른 정렬 기준이 필요한 이번 문제를 푸는데 있어서 Comparator를 사용한 것이다.
위의 로직 자체는 어려울 게 없다.
이 Comparator를 구현하는데 있어서 필요한 함수는 compare 함수이다.
두 가지의 매개변수를 입력 받고 이에 대한 조건과, 정렬 기준을 정하면 된다.
첫 번째 방법인 품질 우선 정렬을 살펴보면, 객체 1과 객체 2의 각 “품질”이 동일하다면 가격이 낮은 순으로 정렬해야하기 때문에 객체 1의 가격과 객체 2의 가격을 뺀다.
이 때 “뺀다.”는 것은 객체 1이 객체 2보다 작다면 음수, 같으면 0, 크면 양수를 반환하게 된다.
이 결과가 음수이면 객체 1의 가격이 객체 2의 가격보다 작다는 것을 의미하고, 정렬 시 객체 1이 객체 2보다 앞에 위치하게 된다.
즉, 오름차순으로 정렬한다는 의미이다.
반대로 아래의 객체 2의 “품질”과 객체 1의 “품질”을 “빼는 것”은 이 결과에 따라 객체 2의 위치가 우선적으로 정해진다.
즉, 내림차순으로 정렬한다는 의미이다.
이 방식을 활용한 것이 Comparator 인터페이스이고, 여러 정렬 조건을 만족해야할 때 사용할 수 있다.
입력된 값을 가공하거나, 출력하는 방식은 그리 어렵지 않다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<Chock> chocks = new ArrayList<>();
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int quality = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());
chocks.add(new Chock(quality, price));
}
// 첫 번째 방법
chocks.sort(new Chock.QualityComp());
System.out.println(chocks.get(0).quality + " " + chocks.get(0).price + " " + chocks.get(1).quality + " " + chocks.get(1).price);
// 두 번째 방법
chocks.sort(new Chock.PriceComp());
System.out.println(chocks.get(0).quality + " " + chocks.get(0).price + " " + chocks.get(1).quality + " " + chocks.get(1).price);
}
}
입력은 n 회 반복하여 촉석루의 개수 만큼 촉석루 객체를 참조하는 리스트를 활용, 이 리스트에 촉석루 객체를 인스턴스화 해서 각 객체의 값을 삽입한다.
이후 출력 시 각 방법에 대한 이너클래스를 찍고 정렬을 사용한 다음, 이 리스트의 0번 째 인덱스, 1번 째 인덱스 값들을 추출해서 출력하면 된다.
전체 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Chock {
int quality;
int price;
public Chock(int quality, int price) {
this.quality = quality;
this.price = price;
}
// 첫 번째 방법 : 품질 우선 정렬, 동일하면 가격이 낮은 순
static class QualityComp implements Comparator<Chock> {
public int compare(Chock c1, Chock c2) {
if (c1.quality == c2.quality) {
return c1.price - c2.price;
}
return c2.quality - c1.quality;
}
}
// 두 번째 방법 : 가격 우선 정렬, 동일하면 품질이 높은 순
static class PriceComp implements Comparator<Chock> {
public int compare(Chock c1, Chock c2) {
if (c1.price == c2.price) {
return c2.quality - c1.quality;
}
return c1.price - c2.price;
}
}
}
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<Chock> chocks = new ArrayList<>();
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int quality = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());
chocks.add(new Chock(quality, price));
}
// 첫 번째 방법
chocks.sort(new Chock.QualityComp());
System.out.println(chocks.get(0).quality + " " + chocks.get(0).price + " " + chocks.get(1).quality + " " + chocks.get(1).price);
// 두 번째 방법
chocks.sort(new Chock.PriceComp());
System.out.println(chocks.get(0).quality + " " + chocks.get(0).price + " " + chocks.get(1).quality + " " + chocks.get(1).price);
}
}
이번 문제는 객체를 활용하고 Comparator 인터페이스를 구현하여 정렬을 사용했다.
이전에는 Comparable 인터페이스를 구현하는 방식을 자주 사용했는데, 이번 문제 처럼 여러 개의 정렬 기준이 있지 않았기 때문이다.
어찌됐든 이번 기회에 Comparator의 사용법에 대해 좀 더 알게되었고, 다음번에 Comparable 인터페이스를 구현해야하는 문제가 있다면 해당 내용도 블로깅할 예정이다.