프로그래머스 코딩테스트 고득점 Kit - Greedy - 체육복
전체 학생 수 n 명 중 m명이 체육복을 잃어버렸고, k명이 여분의 체육복을 갖고 있다. 여분의 체육복을 갖는 k명의 학생이 m명에게 최대한 많이 체육복을 빌려주는 것이 목표이다.
입력 값으로 n, lost 배열, reserve 배열이 주어진다. 체육복을 입을 수 있는 학생의 최대 값을 계산하는 것이 문제이다. (k = lost배열의 길이, m = reserve 배열의 길이)
문제 조건
- 2 <= n <= 30
- m >= 1, m <= n (reserve 배열에는 중복되는 값이 없다.)
- k >= 1 , k <= n (lost 배열에는 중복되는 값이 없다.)
- k명의 학생 중에도 체육복을 도난 당한 학생이 있을 수 있다. 그 경우는 체육복을 빌려주지 못한다.
나는 문제의 마지막 조건을 만족하지 못하는 풀이를 만들어서 일부 테스트케이스를 통과하지 못하는 어려움을 겪었다.
reserve에 속하는 학생 중에도 도난당한 학생이 있다는 것은 그 학생은 체육복을 잃어버린 쪽도, 체육복을 빌려줄 수 있는 쪽도 속하지 않는다는 것이다.
그래서 내가 문제를 해결한 방법은 lost와 reserve의 교집합을 구한 뒤 두 배열에서 교집합을 제거하고 lost[i]-1과 lost[i]+1의 값이 reserve에 있는지 찾는 것이었다.
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public ArrayList<Integer> getIntersection(ArrayList<Integer> lost, ArrayList<Integer> reserve){
ArrayList<Integer> intersection = new ArrayList<>();
for(int i=0; i<lost.size(); i++){
if(reserve.contains(lost.get(i))){
intersection.add(lost.get(i));
}
}
return intersection;
}
public void removeIntersection(ArrayList<Integer> list, ArrayList<Integer> intersection){
for(int i=0; i<intersection.size(); i++){
list.remove(list.indexOf(intersection.get(i)));
}
}
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
ArrayList<Integer> remainStu = new ArrayList<>();
ArrayList<Integer> lostStu = new ArrayList<>();
for(int i=0; i<lost.length; i++){
lostStu.add(lost[i]);
}
for(int i=0; i<reserve.length; i++){
remainStu.add(reserve[i]);
}
ArrayList<Integer> intersectionStu = getIntersection(lostStu, remainStu);
removeIntersection(lostStu, intersectionStu);
removeIntersection(remainStu, intersectionStu);
answer = n - lostStu.size();
Collections.sort(lostStu);
Collections.sort(remainStu);
for(int i=0; i<lostStu.size(); i++){
if(remainStu.indexOf(lostStu.get(i)-1) != -1){
remainStu.remove(remainStu.indexOf(lostStu.get(i)-1));
answer++;
}
else if(remainStu.indexOf(lostStu.get(i)+1) != -1){
remainStu.remove(remainStu.indexOf(lostStu.get(i)+1));
answer++;
}
}
return answer;
}
}