[프로그래머스] 체육복 (Java)

 

문제

프로그래머스

 

알고리즘

그리디, 우선순위 큐

 

풀이

두 리스트를 오름차순으로 정렬하여

잃어버린 학생마다 남은 체육복 중 번호가 맞는 체육복이 있을 때,

작은 번호의 체육복부터 빌리면 가장 많은 학생이 체육 수업을 들을 수 있다.

 

1. lost의 원소 중 reserve에 포함된 원소가 있다면 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우이므로

두 리스트에서 해당 원소를 제거하고 체육복을 빌린 학생 수를 나타낼 count를 1 증가시킨다.

 

2. lost의 리스트를 정렬하고, reserve의 원소들은 우선순위 큐에 삽입한다.

 

3. lost의 각 원소 l마다

l-1 보다 작은 원소는 뒷사람들도 빌릴 수 없으므로 큐에서 삭제하고,

남은 원소들은 l-1과 같거나 큰 원소이므로 그 중 맨 앞에 있는 원소가 l+1보다 같거나 작다면 빌린다.(큐에서 제거 후 count ++)

 

 

코드

import java.util.*;

class Solution {
	public int solution(int n, int[] lost, int[] reserve) {
		ArrayList<Integer> lostList = new ArrayList<>();
		ArrayList<Integer> reserveList = new ArrayList<>();

		int count = 0;
		for (int l : lost)
			lostList.add(l);

		for (int r : reserve) {
			if (lostList.contains(r)) {
				lostList.remove((Object) r);
				count++;
			} else
				reserveList.add(r);
		}

		Collections.sort(lostList);
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int r : reserveList)
			pq.add(r);

		for (int l : lostList) {
			while (!pq.isEmpty() && pq.peek() < l - 1)
				pq.poll();

			if (!pq.isEmpty() && pq.peek() <= l + 1) {
				pq.poll();
				count++;
			}
		}

		return n - lost.length + count;
	}
}