백준 - 라디오( 3135번, JAVA )

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

풀이

• 먼저 a -> b 로 만들 때 1에 해당하는 버튼을 눌렀을 때 값을 변수 m에 저장 ( 가장 안좋은 경우 )
• 리스트로 하면 정렬해야하니 우선순위 큐 선언해서 나중에 가장 작은 수 출력하자 ( 이때 먼저 구해놓은 가장 최악의 수 m을 먼저 저장 )
• 입력한 수가 b보다 크거나 같으면 같아질 때까지 -1 반복해서 카운트
• 입력한 수가 b보다 작으면 같아질 때까지 +1 반복해서 카운트
• 카운트 된 수를 우선순위 큐에 저장
• 우선순위큐에서 가장 작은수 출력 후 +1 해서 첫 버튼 눌렀을 때까지 카운트 해주자
• 항상 리스트 정렬 하느라 시간초과 떴는데 우선순위큐가 너무 좋다.. ( 우선순위큐 == 힙정렬 )

package problem_solving.greedy;

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

public class BaekJoon_3135 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int n = Integer.parseInt(sc.next());
		int m = Math.abs(a-b);
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.offer(m-1);
		while(n-- > 0 ) {
			int cnt = 0 ; 
			int num = Integer.parseInt(sc.next());
			if( num >= b ) {
				while(num !=b ) {					
					cnt+=1;
					num--;
				}
			} else if( num < b){
				while(num!=b) {
					cnt+=1;
					num++;	
				}
			}
			
			pq.offer(cnt);
		}
		
		System.out.println(pq.poll()+1);
		
	}

}