[알고리즘]프로그래머스 코딩테스트 - Greedy : 체육복

서지혜·2023년 6월 2일
0

TIL

목록 보기
7/22

프로그래머스 코딩테스트 고득점 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;    
        
    }
}
profile
개발자가 되고 싶은 감자

0개의 댓글

관련 채용 정보