greedy 알고리즘은 어떤 값을 정렬해놓고 선택해 나갈 때 사용된다. 이게 최선의 방법이라고 생각하기 때문이다.
따라서
- 어떤 값을 정렬하기 위한 Arrays.sort()를 이용한다.
- 구체적인 정렬을 위해 Comparator 인터페이스를 구현해야 한다. 이는 즉 compare를 오버라이딩 해야 한다.
몇 가지 응용문제를 풀면서 개념을 확립해보고자 한다.
응용문제 씨름선수 문제
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 문제에서 사용된다.
A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.
import java.io.*;
import java.util.*;
public class Main{
static class KW {
int key;
int weight;
public KW(int key, int weight){
this.key = key;
this.weight = weight;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
KW[] arr = new KW[N];
StringTokenizer st = null;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[i]= new KW (a,b);
}
Comparator<KW> comp = new Comparator<KW>(){
public int compare(KW x1, KW x2){
return x1.key - x2.key;
}
};
Arrays.sort(arr,comp);
int cnt=1;
for(int i=0;i<N-1;i++){
boolean tag =false;
for(int j=i+1;j<N;j++){
if (arr[i].weight < arr[j].weight) {
tag=true;
}
}
if(tag==false) cnt++;
}
bw.write(Integer.toString(cnt));
bw.flush();
bw.close();
br.close();
}
}
하지만 위의 방법이 정답이긴 했으나 2중 for문을 이용하기 때문에 비효율적인 풀이라고 볼 수 있다.
나는 키를 오름차순으로 정렬해서 2중 for문을 돌도록 해버렸다.
키를 내림차순으로 하면 내려가면서 몸무게의 max값이 갱신될 때마다 그 선수는 선발되는 것이다.
왜냐하면 키와 몸두게 모두 나보다 크거나 많이 나가야 하는데
이미 키를 이미 큰 선수들을 위에 배치했고 내가 그 선수보다 몸무게는 많이 나가야 내가 선발된다. 따라서 내려오면서 나보다 큰 몸무게를 가진 사람이 위에 있으면 안된다.
응용문제 백준의 1931번
을 풀어보자
빨간색으로 표시한 각 번호마다 무엇이 중요한지 체크해보자
1. 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
1 4
4 5
//답 2개2. 시작 시간과 끝나는 시간이 같을 수도 있다.
1 4
4 5
5 5
//답 3개근데 여기서 하나 더 봐야할 것은
1 4
5 5
4 5
//답 2개이렇게 정렬될 수 있다. 따라서 끝나는 시간이 같을 때는 시작 시간을 오름차순으로 정렬하도록 해야 한다.
3. 사실 이 부분은 compare메소드를 오버라이딩 할 때 생각해줘야 하는 부분이다 왜냐하면 오버플로우나 언더플로우가 발생할 수 있기 때문이다. 하지만 이 문제는 두 수 모두 양수여서 underflow나 overflow가 발생하지 않는다.
만약에 음수 - 양수이면 -> 음수가 나오는데 그 음수의 범위가 int의 범위를 넘어설 수도 있다.
만약에 양수 - 음수이면 -> 양수가 나오는데 그 양수의 범위가 int의 범위를 넘어설 수도 있다.
이 2가지를 꼭 유념해서 살펴보자
따라서 아래와 같은 풀이가 나온다.
import java.util.*;
import java.io.*;
public class Main{
static class Meet{
int strt ;
int ed;
public Meet(int strt, int ed) {
this.strt = strt;
this.ed = ed;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Meet[] arr = new Meet[N];
StringTokenizer st = null;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
int strt = Integer.parseInt(st.nextToken());
int ed = Integer.parseInt(st.nextToken());
arr[i] = new Meet(strt, ed);
}
Comparator<Meet> comp = new Comparator<Meet>(){
public int compare(Meet x1, Meet x2){
if(x1.ed == x2.ed) return x1.strt-x2.strt;
else return x1.ed - x2.ed;
}
};
Arrays.sort(arr,comp);
int max = Integer.MIN_VALUE;
int cnt =0;
for(int i=0;i<N;i++){
if(max<=arr[i].strt) {
max = arr[i].ed;
cnt++;
}
}
bw.write(Integer.toString(cnt));
bw.flush();
bw.close();
br.close();
}
}큰 수의 법칙 (이것이 코딩 테스트다)
import jnr.ffi.annotations.In;
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st =new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] input = new int[N];
st=new StringTokenizer(br.readLine()," ");
for(int i=0;i<N;i++){
input[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(input);
int m=0;
int answer =0;
int index=N-1;
int sum=0;
while(M>m){
m++;
if(sum==3) {
answer+=input[index-1];
sum=0;
}
else{answer+=input[index];}
sum++;
}
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
}import jnr.ffi.annotations.In;
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st =new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] input = new int[N];
st=new StringTokenizer(br.readLine()," ");
for(int i=0;i<N;i++){
input[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(input);
int first = input[N-1];
int second = input[N-2];
int answer =0;
answer+= M/(K+1) *K*first;
answer+= (M-(M/(K+1) *K)) * second;
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
}
꾸준하게 Ready, Set, Go!