[프로그래머스/JAVA] 체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

---

- 문제 풀이

1. 도난당하지 않은 학생 수를 기본적으로 계산합니다.
2. 여벌 체육복이 있지만 도난당한 학생을 먼저 처리해 중복을 방지합니다.
3. 나머지 여벌 체육복을 가진 학생들이 앞뒤 학생에게 빌려줄 수 있는지 확인합니다.
4. 최종적으로 체육복을 가진 학생 수를 반환합니다.

---

 

1. 학생 번호 순차적으로 배치 

lost와 reserve 배열을 정렬하여, 학생들의 번호가 순서대로 배치되도록 합니다.

import java.util.*;

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

        // 1. 학생들 번호 순차적으로 배치
        Arrays.sort(lost);
        Arrays.sort(reserve);

 

 

+ 정렬안할 경우?

1. 순차적 탐색이 어려워짐: 정렬을 하지 않으면 학생 번호가 불규칙하게 섞여 있으므로, 빌려줄 수 있는 학생을 찾는 것이 복잡해집니다. 예를 들어, lost = [4, 1], reserve = [5, 3]일 때, 앞뒤 관계를 고려해 탐색하는 것이 어려워질 수 있습니다.
2. 정답을 찾기 어려워짐: 예를 들어, 정렬되지 않은 상태에서는 lost[i] - 1 == reserve[j] 또는 lost[i] + 1 == reserve[j] 조건을 만족하는 학생을 찾는 과정에서 일부 학생을 건너뛰게 되어 정확한 결과를 얻지 못할 수 있습니다.

 

 

2. 도난당하지 않은 학생 수 계산

// 2. 도난당하지 않은 학생 수 계산
        answer += n - lost.length;

우선 전체 학생 수에서 도난당한 학생 수를 빼서 기본적으로 체육복을 가진 학생 수를 구합니다.

 

 

 

 

3. 여벌이 있지만 도난당한 학생 처리

// 3. 여벌이 있지만 도난당한 학생 처리(자기자신이 입어야함)
        //    ex) lost -> [2]  reserve -> [2]
        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;
                }
            }
        }

 

여벌 체육복을 가져왔지만 도난당한 학생들을 먼저 처리합니다.

즉, 여벌이 있으면 자기 자신이 입을 수 있으므로, 다른 학생에게 빌려줄 수 없기 때문에 해당 학생들을 먼저 처리하여 lost와 reserve 배열에서 제외시킵니다.

이를 위해 lost[i]와 reserve[j]가 같을 때 그 학생들은 이미 체육복을 갖고 있다고 보고, 배열에서 제거하는 대신 -1로 표시합니다.

 

 

 

 

 

4. 다른 학생에게 체육복을 빌려주는 로직

// 4. 다른 학생에게 체육복 빌려줌
        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;
                }
            }
        }

 

이제, 여벌 체육복을 가진 학생들이 앞번호나 뒷번호 학생들에게 체육복을 빌려주는 과정을 처리합니다. lost[i] - 1 == reserve[j] 또는 lost[i] + 1 == reserve[j] 조건을 통해, 빌려줄 수 있는 경우를 확인합니다. 체육복을 빌려준 학생(reserve[j])은 더 이상 다른 학생에게 빌려줄 수 없으므로, reserve[j]를 -1로 표시해 다시 사용되지 않도록 합니다.

 

 

---

 

 

 

- 정답 코드

import java.util.*;

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

        // 1. 학생들 번호 순차적으로 배치
        Arrays.sort(lost);
        Arrays.sort(reserve);

        // 2. 도난당하지 않은 학생 수 계산
        answer += n - lost.length;

        // 3. 여벌이 있지만 도난당한 학생 처리(자기자신이 입어야함)
        //    ex) lost -> [2]  reserve -> [2]
        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;
                }
            }
        }

        // 4. 다른 학생에게 체육복 빌려줌
        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;

    }
}