[프로그래머스 코딩테스트] 탐욕법(Greedy) - 체육복

이거 왜 채점 결과 90점인지... 알 수가 없다... 답답하네 ㄱㅡ

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length; // 도난 당하지 않은 학생 수 
        
        // 정렬
        Arrays.sort(lost);
        Arrays.sort(reserve);
        
        for (int i=0; i<lost.length; i++) {
            for (int j=0; j<reserve.length; j++) {
                
                System.out.println("lost > " + lost[i] + " reserve > " + reserve[j] );
                                    
                    if (lost[i] == reserve[j] || Math.abs(lost[i] - reserve[j]) == 1) {
                        // 나 자신이 여벌을 입어야 함 or 앞뒤 친구에게 빌려줄 수 있는 상황 > 수업 들을 수 있는 학생 수 +1, index 초기화
                        answer++;
                        reserve[j] = -1; // 다시는 빌려줄 수 없으므로 index값 초기화
                        break;
                    }
                
            }    
        }
        
        return answer;
    }
}

여벌이 있는데 도난 당한 학생의 경우를 먼저 처리 해주니까 100점으로 나왔다.

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length; // 도난 당하지 않은 학생 수 
        
        // 정렬
        Arrays.sort(lost);
        Arrays.sort(reserve);
                
        for (int i=0; i<lost.length; i++) {
            for (int j=0; j<reserve.length; j++) {
                if (lost[i] == reserve[j] ) {
                    // 나 자신이 여벌을 입어야 함 > 수업 들을 수 있는 학생 수 +1, index 초기화
                    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 ( Math.abs(lost[i] - reserve[j]) == 1) {
                    // 앞뒤 친구에게 빌려줄 수 있는 상황 > 수업 들을 수 있는 학생 수 +1, index 초기화
                    answer++;
                    reserve[j] = -1; // 다시는 빌려줄 수 없으므로 index값 초기화
                    break;
                }
            }
        }
        
        return answer;
    }
}

다른 사람 풀이 참고해서 풀어본 방식.

이 방식으로 하니까 0.02ms 정도 나오고, 위의 방식으로 하면 0.36ms 정도 나오는걸로 봐서... 이 방식이 더 좋은 것 같다.

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] student = new int[n]; // 0으로 초기화 된 n명의 학생들
        int answer = n;
        
        // 도난당한 학생은 -1, 여분이 있는 학생은 +1 처리 -> 여분이 있는 학생이 도난당한 경우 0처리 됨
        for (int i : lost)
            student[i-1]--;
        for (int i : reserve)
            student[i-1]++;
        
        // for문으로 도난당한 학생 처리
        for (int i=0; i<student.length; i++) {
            if (student[i] == -1) { // 도난당한 학생
                int iPrev = i-1;
                int iNext = i+1;
                
                if (iPrev >= 0 && student[iPrev] == 1) {
                    student[i]++;
                    student[iPrev]--;
                } else if (iNext < student.length && student[iNext] == 1) {
                    student[i]++;
                    student[iNext]--;
                } else {
                    answer--;
                }            
            }
        }
        
        return answer;
    }
}