백준 - 이장님 초대 ( 9237번, JAVA )

Greedy ( https://www.acmicpc.net/problem/9237 )

풀이

• 문제의 포인트는 ( 심어야하는날수 + 심는날의 날짜 + 심는데 걸리는 하루 ) 이거다.
• Integer 컬렉션 배열을 사용해서 내림차순 정렬해서 풀 수도 있는데 나는 우선순위큐를 써서 풀어봤다. 항상 뭔가 자료구조상 정렬보다는 우선순위큐를 사용하는게 더 빠르다는 생각이 들어서 ..

• 컬렉션 내림차순 정렬을 사용한 코드

package problem_solving.greedy;

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

public class BaekJoon_9237 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = Integer.parseInt(sc.next());
		Integer [] arr = new Integer[t];
		for(int i= 0 ; i <t ; i++) {
			arr[i] = Integer.parseInt(sc.next());
		}
		
		Arrays.sort(arr, Collections.reverseOrder());
		
		int max = 0 ;
		for(int i = 0 ; i<arr.length;i++) {
			max = Math.max(max, arr[i] + i + 1);
		}
		
		System.out.println(max+1);
	}

}

• 우선순위큐를 사용한 코드

package problem_solving.greedy;

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

public class BaekJoon_9237 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
		int t = Integer.parseInt(sc.next());
		for(int i= 0 ; i <t ; i++) {
			pq.offer(Integer.parseInt(sc.next()));
		}
		int max = 0;
		int day = 0  ;
		while(!pq.isEmpty()) {
			max = Math.max(max, pq.poll()+1+day++);
		}
		
		System.out.println(max+1);
	}

}

차이점

• 속도도 거의 차이가 나지 않는다. 일단 두 가지로 풀어보는 방법을 아는게 중요하니까 gooooood