[백준] 알고리즘 분류(그리디 알고리즘,JAVA)27313번, 효율적인 애니메이션 감상

문제 링크

27313번: 효율적인 애니메이션 감상

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 한별이는 애니메이션이 끝남과 동시에 볼 수 있으며, 동시에 K개를 볼 수 있다.

2. 한별이는 M시간까지만 애니메이션을 볼 수 있습니다.

3. M시간까지 볼 수 있는 애니메이션의 최대 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 애니메이션 시간을 오름차순 정렬한 뒤, 우선순위 큐를 이용하여 최대 볼 수 있는 개수를 탐색합니다.

 

3. 최대 볼 수 있는 개수를 결과로 출력합니다.

 

 

애니메이션 시청 탐색!

 

먼저 M보다 시청 시간이 긴 애니메이션은 어차피 보지 못하므로 List에 저장되지 않도록 하였습니다.

 

볼 수 있는 애니메이션을 모두 저장한 뒤 오름차순으로 정렬하였습니다.

 

탐색 진행

 

우선순위 큐에는 한별이가 동시에 보고 있는 애니메이션을 저장합니다.

 

최대 애니메이션 개수를 구하려면 최대한 한별이는 애니메이션을 동시에 시청해야 합니다.

 

우선순위 큐의 크기 < K가 성립할 때

 

애니메이션을 우선순위 큐에 저장!

 

우선순위 큐의 크기 = K가 성립할 때

 

우선순위 큐도 오름차순 정렬되었기 때문에 peek()값은 가장 빨리 끝나는 애니메이션이 담겨져있습니다.

 

peek() + 애니메이션 시간 <= M

 

: 해당 애니메이션을 볼 수 있습니다.

 

peek() + 애니메이션 시간 > M: 해당 애니메이션과 이후 애니메이션은 더 이상 볼 수 없으므로 탐색을 종료합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

N = 2

M = 3

K = 4

 

	애니1	애니2
시간	3	4

 

2. 애니메이션 시간을 오름차순 정렬한 뒤, 우선순위 큐를 이용하여 최대 볼 수 있는 개수를 탐색합니다.

 

M보다 큰 애니메이션 제거!

 

	애니1
시간	3

 

오름차순 정렬!

	애니1
시간	3

 

우선순위 큐를 이용한 탐색!

 

	애니1
시간	3

 

우선 순위 큐 크기(0) < K(4) 성립!

 

애니1 시청!

 

모든 애니 시청 완료!

 

3. 최대 볼 수 있는 개수를 결과로 출력합니다.

 

리스트에 저장된 모든 애니를 시청 완료 : 1개

1을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 애니메이션 정보를 띄어쓰기 기준으로 나누었습니다.
• M이하의 애니메이션을 리스트에 저장한 뒤 오름차순 정렬합니다.
• 우선순위 큐를 이용하여 한별이가 볼 수 있는 최대 애니메이션 개수를 탐색합니다.
• 시청한 애니메이션 최대 개수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        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());
        ArrayList<Integer> list = new ArrayList<>();	//M 이하의 애니메이션 저장 리스트
        st = new StringTokenizer(br.readLine()," ");
        //M시간 이하의 애니메이션 리스트에 저장
        for(int i=0;i<N;i++){
            int t = Integer.parseInt(st.nextToken());
            if(t <= M)
                list.add(t);
        }
        Collections.sort(list);	//애니메이션 시간 오름차순 정렬
        if(list.size() == 0)	//애니메이션이 존재하지 않을 때
            bw.write("0");
        else{		//애니메이션 존재할 때
            //동시에 시청하고 있는 애니메이션 저장 우선순위 큐
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            pq.add(list.get(0));	//첫 번째 애니메이션 저장
            int answer = 1;
            //2번째 애니메이션부터 시청 시작!
            for(int i=1;i<list.size();i++){
                //우선순위 큐 크기 == K 성립!
                if(pq.size() == K){
                    if(pq.peek() + list.get(i) > M)	//M을 벗어나면 더 이상 시청 불가능!
                        break;		//탐색 종료!
                    else
                        pq.add(pq.poll() + list.get(i));	//M이하이면 시청!
                }else	//우선순위 큐 크기 < K 성립!
                    pq.add(list.get(i));	//애니메이션 시청!
                answer++;
            }
            bw.write(answer + "");	//시청한 애니메이션 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}