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

\

📑 1. 문제설명

---

💡 2. 접근방식

문제에서 주어진 것

• n : 전체 학생의 수
• lost : 체육복 도난당한 학생들의 번호들  (배열) 
• reserve : 여벌 가져온 학생 번호들 (배열)

체육복은 앞,뒤 번호 학생 에만 빌려줄 수 있음.
도난 당한 학생들은 여분이 없어서 체육복 빌려줄 수 없음.

---

1. `lost`와 `reserve` 배열 정렬

 

2. 체육수업에 참여할 수 있는 학생의 수 = 체육복이 있거나 빌릴 수 있는 학생들의 수

 `체육복을 도난 당하지 않은 학생의 수` + `도난당했지만 예비로 들고 온 학생의 수` + `도난당했지만 체육복을 빌릴 수 있는 학생의 수`

이 모든 학생들의 수를 누적해서 answer 변수에 담아 준다. 

---

 

✅ 체육복을 도난 당하지 않은 학생의 수

= 전체 학생의 수 - 체육복을 도난당한 학생 의 수

`n - lost.length`

✅ 도난당했지만 예비로 들고 온 학생의 수

- `lost`배열과 `reserve`배열에 둘다 있는 학생은 본인 체육복은 있지만 빌려줄 수 없다.

- 체육복이 있어 체육수업을 들을 수 있기 때문에 answer에 더해준다.

- 다른 학생에게 체육복을 빌릴 필요가 없으므로 lost[i]에 상관없는 값 -1 저장해서 해당 배열에서 제외해준다.
- 마찬가지로 다른 학생에게 빌려줄 수 없으므로 reserve[i]에 -1 저장해서 해당 배열에서 제외.

✅ 도난당했지만 체육복을 빌릴 수 있는 학생의 수

- 체육복을 현재 학생의 앞뒤 번호 학생에게만 빌릴 수 있다.

- 앞의 학생에게 빌릴 수 있음 `lost[i] - 1 == reserve[j] ` 또는

- 뒤의 학생에게 빌릴 수 있음 `lost[i] + 1 == reserve[j]`
- 체육복을 빌렸다면 answer에 누적해준다.

- 체육복을 이미 빌려줬으므로 reserve[j]에 -1 를 저장해서 제외해준다. 

---

⭐ 3. 정답코드

내가 푼 코드

import java.util.Arrays;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;

		// 배열 정렬
		Arrays.sort(reserve);
		Arrays.sort(lost);

		// 체육복 도난당하지 않은 학생 수
		// 전체학생수 - 도난당한 학생 수
		answer = n - lost.length;

		// 여벌 체육복 가져왔으나 도난당한 학생 수
		// 체육시간에 참여할 수 있으나 다른 학생에게 빌려줄 수 없으므로
		// lost 배열과 reserve 배열에서 해당 학생의 번호를 삭제해 주어야 함.
		// 나는 상관 없는 값 -1로 설정해 줌
		for (int i = 0; i < lost.length; i++) {
			for (int j = 0; j < reserve.length; j++) {
				if (lost[i] == reserve[j]) {
					answer++;
					lost[i] = -1;
					reserve[j] = -1;
					break;
				}
			}
		}
		// 도난당했지만 체육복을 빌릴 수 있는 학생 수
		for (int i = 0; i < lost.length; i++) {
			for (int j = 0; j < reserve.length; j++) {
				if (lost[i] - 1 == reserve[j] || lost[i] + 1 == reserve[j]) {
					answer++;
					reserve[j] = -1;
					break;
				}
			}
		}
		return answer;
    }
}

 

테스트용 코드

public class programmers {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		int[] lost = { 2, 4 };
		int[] reserve = { 1, 3, 5 };
		
		int result = Solution.solution(n, lost, reserve);
        System.out.println("체육복을 입을 수 있는 학생 수: " + result);
	}
}

 

저처럼 메인에서 테스트 할 때 객체를 생성하지 않고, 클래스 이름으로 바로 solution 메서드를 호출하려면 Solution 메서드를 `static` 메서드로 바꿔야 합니다. solution 메서드를 인스턴스 메서드로 정의하시면 인스턴스 먼저 생성하셔서 해야 해요. 안그러면 오류 뜹니다~

👏🏻 좋아요 가장 많이 받은 코드

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] people = new int[n];
        int answer = n;

        for (int l : lost) 
            people[l-1]--;
        for (int r : reserve) 
            people[r-1]++;

        for (int i = 0; i < people.length; i++) {
            if(people[i] == -1) {
                if(i-1>=0 && people[i-1] == 1) {
                    people[i]++;
                    people[i-1]--;
                }else if(i+1< people.length && people[i+1] == 1) {
                    people[i]++;
                    people[i+1]--;
                }else 
                    answer--;
            }
        }
        return answer;
    }
}

---

🐦 4. 같은 유형 문제 (그리디)

https://awesomepossum.tistory.com/436

[프로그래머스] (Java) 조이스틱 (그리디)