[탐욕법(Greedy)] 체육복_Java

코딩테스트 고득점 Kit_탐욕법(Greedy)

🔥 체육복 🔥

탐욕법 알고리즘에 대한 설명은 다른 post 참고!

---

👀 문제

점심시간에 도둑이 들어서 일부 학생들의 체육복을 도난당했다.
여벌이 있는 학생들이 이들에게 체육복을 빌려주려하는데 학생들의 번호는 체격순으로 매겨져 있어 바로 앞과 뒷번호의 학생들에게만 체육복을 빌려줄 수 있습니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reverse가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return하도록 solution을 완성해보자

---

✔️ 조건

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

---

👩‍💻 입력 & 🧙 출력

n	lost	reserve	return
5	[2,4]	[1,3,5]	5
5	[2,4]	[3]	4
3	[3]	[1]	2

---

🙋‍♀️ 첫번째 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        
    
        int answer = n;
     
        answer = n-lost.length;
        
        //도난당했지만 여분이 있는 경우
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                 //System.out.println(lost[i]+"와 "+reserve[j]);
                if(lost[i] == reserve[j]){
                    reserve[j] = -1;
                    lost[i] = -1;
                    answer = answer+1;
                    //도난당했지만 여분이 있는 학생은 빌려줄수 없지만 체육시간에 참여가능하니까 제외
                   System.out.println(lost[i]+"와 "+reserve[j]);
                }                
            }
        }
        
        //reserve에 있는 학생들의 앞뒤번호 학생이 lost에 있다면
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                if(lost[i] != -1 && reserve[j] !=-1){
                    if(lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1){
                        System.out.println(lost[i]+"가 "+reserve[j]+"꺼를 빌려");
                        lost[i] = -1;
                        reserve[j] = -1;
                        
                        answer +=1;
                    }    
                }
                
            }
        }
        return answer;
    }
}

처음에는 lost와 reserve가 정렬되어있지 않을 것이라고는 생각하지 못해서 정렬을 하지 않고 코드를 작성해서 실패가 발생했다.

🙋‍♀️ 두번째 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);
    
        int answer = n-lost.length;

        
        //도난당했지만 여분이 있는 경우
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                 //System.out.println(lost[i]+"와 "+reserve[j]);
                if(lost[i] == reserve[j]){
                    reserve[j] = -1;
                    lost[i] = -1;
                    answer = answer+1;
                    //도난당했지만 여분이 있는 학생은 빌려줄수 없지만 체육시간에 참여가능하니까 제외
                   System.out.println(lost[i]+"와 "+reserve[j]);
                }                
            }
        }
        
        //reserve에 있는 학생들의 앞뒤번호 학생이 lost에 있다면
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                if(lost[i] != -1 && reserve[j] !=-1){
                    if(lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1){
                        System.out.println(lost[i]+"가 "+reserve[j]+"꺼를 빌려");
                        lost[i] = -1;
                        reserve[j] = -1;
                        
                        answer +=1;
                    }    
                }
                
            }
        }
        
        
        
        return answer;
    }
}

1. Arrays.sort를 통해서 lost와 reserve를 정렬해주었다.
2. answer의 초기값을 전체 학생수에서 잃어버린 학생수 만큼 뺀값으로 대입한다.
3. 첫번째로 도난당했지만 여분이 있는 학생들을 찾아서 해당 인덱스의 값을 -1로 변경해준다.
   그리고 해당 학생들은 여분이 있어서 체육수업에 참여할 수 있으므로 answer에 값을 +1해준다.
4. 두번째로는 reserve에 있는 학생들의 앞뒤 번호 학생이 lost한 학생일 경우를 구해준다.
   여기서 중요한 점은 lost[i]와 reserve[ㅓ]의 값이 -1인 학생은 제외시켜야한다는 점이다.
   그후, lost의 i번째가 reserve의 j번째 -1 번째 또는 +1 번째에 존재한다면 해당 인덱스번째의 값을 -1로 대입해주고 answer에 +1을 해준다.

---

👏 마무리

체육복 도둑질 하지 마세요