알고리즘 및 코테 복습 - 그리디 (Greedy)

⬛ 06. 그리디

⬛ 06-1. 그리디 알고리즘

• 현재 상태에서 보는 선택지 중 최선의 선택지를 전체 선택지의 최선이라고 가정하는 알고리즘
• 그리디 알고리즘 적용 직전에 대상 데이터들을 (오름차순/내림차순) 정렬해두는 경우 多

현재 기준값을 기준으로 비교하고, 비교 한 뒤 현재의 기준값이 계속 갱신되는 행위 반복하는 것 !

⬛ 그리디 접근 방식

• 1) 객체화 시켜서 각 필드의 값들에 대하여 객체의 compareTo 사용하여 정렬시키고, 최초 0번 값을 기준값으로 하여 비교한 뒤, 기준값 갱신시키는 방식

ex) 신입사원
class Sawon implements Comparable<Sawon>{
	//필드
 	 ... 
 	 //생성자
  	 ... 
  	@Override
	public int compareTo(Sawon o) {
    	return 조건 
    
    };

• 2) 배열화 시켜서 Arrays.sort(배열, (a,b) → a[0]-b[0] ); 정렬시키고, 기준값을 갱신

 int line[][] = new int[n][2];
 for(int i=0; i<n; i++){
		line[i][0] = 특정 기준;
		line[i][1] = 특정 기준;
 }
--> 여기서 i로는 각 인덱스 객체찍고, 0번에 특정값, 1번에 특정값 담아준다고 생각할 것.


//정렬 -오름차순 
 Arrays.sort(line, (a, b) -> (a[1] - b[1] ));
 //정렬- 내림차순
 Arrays.sort(line, (a, b) -> (b[1] - a[1] ));

---

🟦 백준 1715번. 카드 정렬하기

• 적은 묶음 두 개씩 우선순위 큐에 담아가면서 합치고 pQ에 다시 담는 활동을 size 가 1 아닌 동안 반복하면 된다.

import java.util.PriorityQueue;
import java.util.Scanner;

/*1715번. 카드 정렬하기 */
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();//묶음 개수 
		int[] arr= new int[N];
		for(int i=0; i<N; i++) arr[i] = kb.nextInt();
		//우선순위 큐 자동 오름차순 정렬 
		PriorityQueue<Integer> pQ = new PriorityQueue<>();
		
		for(int i=0; i<N; i++) {
			pQ.add(arr[i]);//자동 우선순위 정렬 될건데 
		}
		int answer = 0;
		
		while(pQ.size() != 1){
		 	int a = pQ.poll();
		 	int b = pQ.poll();
		 	answer += (a+b);
		 	pQ.add(a+b);//다시 담기 
		}
		System.out.println(answer);
	}
}

---

🟦 백준 1931번. 회의실

• 회의실 객체 하나 만들어서 종료 시간 기준 정렬해놓은 뒤, 만약 종료 시간 같다면 시작 시간 우선으로,
• 이제 차례로 arr 순회하면서 현재 회의의 종료시간보다 크거나 같은 시작 시간의 회의 발견 시, answer++ 후 ed 종료 시간을 갱신시킨다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/*1931번. 회의실 배정 */
class Heai implements Comparable<Heai>{
	int st, ed;
	Heai(int st, int ed){
		this.st = st;
		this.ed = ed;
	}
	@Override
	public int compareTo(Heai o) {
		if(this.ed == o.ed) {//종료 시간 같다면
			return this.st - o.st;//시작 시간 기준 오름차순 
		}
		return this.ed - o.ed;//종료 시간 기준 오름차순 
	}
}
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		
		ArrayList<Heai> arr = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			int a = kb.nextInt();
			int b=  kb.nextInt();
			arr.add(new Heai(a, b));//객체 담고 
		}
		//저 기준대로 정렬 
		Collections.sort(arr);
		
		//그리디 알고리즘 - 종료 시간 기준 정렬 해놓고,선택 한 종료 시간보다 크거나 같은 시작 시간 갖는 애 택 
		int answer= 1;//일단 얘는 한다 생각 하고 카운팅 
		int ed = arr.get(0).ed; //첫번쨰 종료 시간   
		for(int i=1; i<N; i++) {
			if(ed <= arr.get(i).st) {//현재 끝 시간 다음에 올 수 있는 시작 회의 발견 시 
				answer++;//누적 
				ed = arr.get(i).ed;//얘로 갱신
			}
		}
		//정답 출력 
		System.out.println(answer);		
	}
}

---

🟦 백준 1946번. 신입 사원

• 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발
• = 하나라도 떨어지면 탈락
• 그러므로 서류성적 높은 사람 우선 정렬 시켜놓은 다음에, (현재 선택한 사람은 어쨋든 서류가 젤 높은 사람이고) 이 사람보다 면접 마저 떨어지는 사람 발견 시 탈락

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

//신입 사원 
class Sawon implements Comparable<Sawon>{
	int s;//서류
	int m;//면접
	Sawon(int s, int m){
		this.s= s;
		this.m = m;
	}
	@Override
	public int compareTo(Sawon o) {
		// TODO Auto-generated method stub
		if(this.s == o.s) {
			return this.m - o.m;//같으면 면접 오름차순 정렬 
		}
		return this.s-o.s;//성적 등수 기준 오름차순 정렬 
	}
}
public class Main {
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int T = kb.nextInt();
		ArrayList<Integer> answer= new ArrayList<>();//정답용 
		
		for(int t = 0; t<T; t++) {
			int N = kb.nextInt();//사람 수 
			ArrayList<Sawon> arr = new ArrayList<>();
			
			for(int i=0; i<N; i++) {
				int a = kb.nextInt();
				int b = kb.nextInt();
				arr.add(new Sawon(a, b));//성적, 면접 담기 
			}
			//아까 기준대로 정렬시킴
			Collections.sort(arr);
			int cnt= 1;
			int target = arr.get(0).m;
			//그리디 - 서류 높은 순서대로 니까. 이제 현재 애보다 면접 등수 낮으면 탈락 
			for(int i=1; i<N; i++) { //뒤부터 돌면서 
				if(target > arr.get(i).m) { //타겟보다 더 높은 면접 점수 갖는 애 발견 시 
					cnt++;
					target = arr.get(i).m;//면접 기준 점수 갱신 
				}
			}
			//정답 세팅 
			answer.add(cnt);//현재 카운팅
		}
		//답 출력 
		for(int x : answer )System.out.println(x);
	}
}

---

🟦 침몰하는 타이타닉 | 그리디, 투포인터

• 투포인터, 그리디로 풀었다.
• 최대한 많이 태워야 보트 사용이 최소가 된다.
• 즉, 남아있는 가장 작은 값 + 가장 큰 값을 처리해서 빈틈없이 매워야 한다.
• 일단, 정렬시켜놓고, 두명의 합이 기준 값 m보다 큰지 작은지 구분시켰다.

1) 두 명의 합이 m보다 크면

• R로 찍은 값 한명만 태운다는 뜻으로 R감소 후 answer++

2) 두 명의 합이 m보다 작거나 같으면

• L++, R—:즉 둘다 처리했다 이거임. answer++

package to_0719_1;
//침몰하는 타이타닉
import java.util.*;
class Solution {
	
	//솔루션 함수 
	public int solution(int[] nums, int m){//N명, Mkg 이하 
		int answer = 0;
		//데이터 정렬시킴
		Arrays.sort(nums);
		int L = 0;
		int R = nums.length -1;
		
		int sum;
		
		while(L <= R) {
			sum = nums[L] + nums[R];
			if(sum > m ) { // 두 값의 합이 m보다 큰 경우, 그냥 answer++처리 후. R-- | 한개만 담는다 이뜻 
				answer++;
				R--;
			}else if(sum <=m) {//작거나 같으면 둘 다 담을 수 있다는 것이므로 
				answer++;
				L++;
				R--;//두 개 다 처리했다는 뜻으로 움직임 
			}
		}
		
		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{90, 50, 70, 100, 60}, 140));
		System.out.println(T.solution(new int[]{10, 20, 30, 40, 50, 60, 70, 80, 90}, 100));
		System.out.println(T.solution(new int[]{68, 72, 30, 105, 55, 115, 36, 67, 119, 111, 95, 24, 25, 80, 55, 85, 75, 83, 21, 81}, 120));
	}
}

---

🟦 최소 이동 횟수

• 최소로 이동하고 싶다는 본 뜻 = 한 번에 가장 많이 들고 가겠다는 말
• 배열 정렬시켜놓고, 양쪽 끝에서 찍은 값이 남아있는 데이터들 중 (가장 작은 + 가장 큰)의 합이 된다.
• 직전 문제와 비슷하다.

//최소 이동 횟수 : 최소로 이동하고 싶다. = 한 번에 최대한 많이 들고가고 싶다.
import java.util.*;

class Solution {
	//솔루션 함수 
	public int solution(int[] nums){
		int answer = 0;
		int pivot = 5;//기준값이 될 거고
		
		//정렬 시킴 
		Arrays.sort(nums);
		
		int L = 0, R=nums.length-1;//양쪽 끝 지칭시켜놓고 
		int sum;
		while(L <= R) {
			sum = nums[L] + nums[R];
			if(sum > pivot) {
				R--;//큰 것만 담고 이동 
				answer++;
			}else if(sum <= pivot) {
				L++;
				R--;
				answer++;
			}
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{2, 5, 3, 4, 2, 3}));
		System.out.println(T.solution(new int[]{2, 3, 4, 5}));
		System.out.println(T.solution(new int[]{3, 3, 3, 3, 3}));
	}
}

---

🟦 전투 게임 | 그리디

• 객체에 정보를 담아두고, 객체 정렬 기준을 공격력 (점수 높은 애 기준) 내림차순 되도록 둔다.
• 핵심은 정렬된 상태에서 현재 i로 찍은 기준 점수보다 j로 찍은 뒷 학생들은 점수가 모두 작을 수 밖에 없다
• 다른 팀이면서 점수가 작을 떄, answer의 해당 num 으로 값을 누적시킨다.

package to_0719_3;
import java.util.*;
//전투게임 
class Student implements Comparable<Student>{
	int num;//번호 
	char team;//팀 구분 
	int score;//공격력
	Student(int num, char team, int score){
		this.num = num;
		this.team = team;
		this.score = score;
	}
	@Override
	public int compareTo(Student o) {
		return o.score - this.score;//역순 내림차순 정렬 (큰 -작은)
	}
}
class Solution {
	//솔루션 함수 
	public int[] solution(String[] students){
		int n = students.length;
		int[] answer = new int[n];
		
		ArrayList<Student> arr = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			char a = students[i].split(" ")[0].charAt(0);//첫번쨰 값은 팀으로 
			int b = Integer.parseInt(students[i].split(" ")[1]);
			
			arr.add(new Student(i, a, b));//차례대로 객체 집어넣고 
		}
		//공격력 기준 정렬 
		Collections.sort(arr);
		
		for(int i=0; i<arr.size(); i++) {
			//현재 i를 기준값으로 
			int num = arr.get(i).num;
			char t = arr.get(i).team;
			int sc = arr.get(i).score;
			
			for(int j=i; j<arr.size(); j++) { //그 뒷부분 돌면서 점수 쌓고 
				if(t != arr.get(j).team && sc > arr.get(j).score) { //현재보다 공격력 작은 애 발견할 때마다 
					answer[num] += arr.get(j).score;//여기서 누적시키고  
				}
			}
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(Arrays.toString(T.solution(new String[]{"a 20", "b 12", "a 10", "c 11", "e 12"})));
		System.out.println(Arrays.toString(T.solution(new String[]{"a 17", "b 12", "a 10", "c 11", "b 24", "a 25", "b 12"})));
		System.out.println(Arrays.toString(T.solution(new String[]{"b 20", "c 15", "a 200", "b 11", "b 24", "a 25", "b 12"})));
		System.out.println(Arrays.toString(T.solution(new String[]{"a 30", "a 25", "a 25", "b 20", "b 25", "a 25", "b 30"})));
	}
}

---

🟦 스프링 쿨러 - 그리디

• line[i][0] 에는 좌표 시작값, line[i][1] 에는 좌표 끝값을 담아주고 각 로프 i에 대하여 담아준다.
• st 보다 작거나 같은 시작점을 가진 애들 중에선, ed값이 가장 큰 (즉 범위 많이 커버 가능한) 애들을 선택하고 갱신시킨다.

import java.util.*;
//스프링쿨러 문제 풀이
class Solution {
	public int solution(int n, int[] nums){
		int answer = 0; 
		int[][] line = new int[nums.length+1][2];
		//세팅  
		for(int i=0; i<=n; i++) {//각 로프i를 사용했을 때
			line[i][0] = Math.max(0, i-nums[i]);//범위 시작값 (0은 안벗어나게)
			line[i][1] = Math.min(n, i+nums[i]);//범위 끝값  (n은 안벗어나게) 
		}
		//왼쪽 시작값 기준 오름차순 정렬
		Arrays.sort(line, (a, b)-> a[0]-b[0]);//시작값 기준 정렬 
		
		int st = 0, ed = 0, i=0;
		while(i<line.length) {
			//시작점이 st보다 작거나 같은 스프링쿨러들 중에서 가장 길게 뿌릴 수 있는 애 찾는 거임 
			while(line[i][0] <= st) {
				ed = Math.max(ed, line[i][1]);	//끝점이 기존ed보다 큰 애 발견 시, 갱신
				i++;
			}
			answer++;
			if(ed == n) return answer; //끝점 다으면 종료
			//위를 거쳐왔는데 ed값이 갱신 안되고 st=ed값이 됐다면 조건에 만족하는 애 없다는 거니 -1 리턴
			if(st == ed) return -1; //시작점이 ed가 되어 버리면 -1리턴
			st = ed;//이제 시작점을 다시 끝점으로 갱신 <-얘를 기준으로 선택
		}
		return answer;
	}
	//실행 메인 
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(8, new int[]{1, 1, 1, 2, 1, 1, 2, 1, 1}));
		System.out.println(T.solution(4, new int[]{1, 2, 2, 0, 0}));		
		System.out.println(T.solution(5, new int[]{2, 0, 0, 0, 0, 2}));
		System.out.println(T.solution(11, new int[]{1, 2, 3, 1, 2, 1, 1, 2, 1, 1, 1, 1}));
	}
}

---

🟦 꽃이 피는 최단 시간

• 심는 시간은 겹쳐서는 안된다.
• flower[i][0] = 심는 시간, flower[i][1] = 성장 시간으로 둔다.
• 성장시간 기준으로 역순 정렬 (큰 -> 작은)
• 차례로 시작 점 = 직전 꽃의 심는 시간으로 갱신해주면서 가장 큰 최종 시간을 answer로 갱신 

package to_0724_6;
import java.util.*;
class Solution {
	//솔루션 함수 
	public int solution(int[] plantTime, int[] growTime){
		int answer = 0;
		int n = growTime.length;
		int[][] flower = new int[n][2];
		for(int i=0; i<n; i++) {
			flower[i][0] = plantTime[i];
			flower[i][1] = growTime[i];
		}
		//정렬-성장시간 역순
		Arrays.sort(flower, (a,b) -> (b[1]- a[1]));
		
		//그리디
		int st=0, ed = 0;
		for(int[] x : flower) {
			ed = st + x[0] + x[1];//시작+심기+성장
			answer = Math.max(answer, ed);
			st += x[0];//성장시간 
		}	
		return answer;
	}
	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[]{1, 3, 2}, new int[]{2, 3, 2}));
		System.out.println(T.solution(new int[]{2, 1, 4, 3}, new int[]{2, 5, 3, 1}));
		System.out.println(T.solution(new int[]{1, 1, 1}, new int[]{7, 3, 2}));
		System.out.println(T.solution(new int[]{5, 7, 10, 15, 7, 3, 5}, new int[]{6, 7, 2, 10, 15, 6, 7}));
		System.out.println(T.solution(new int[]{1, 2, 3, 4, 5, 6, 7}, new int[]{7, 5, 4, 3, 2, 1, 6}));
	}
}