import java.util.*;
import java.util.stream.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
/*
체격순 번호의 앞 뒤만 가능
e.g. 5<-4->3
하나 차이만 가능
최대한 많은 학생
전체 학생 수 : n
도난당한 학생 번호 : lost
여벌 학생 번호 : reserve
*/
int finalLost = lost.length;
Arrays.sort(lost);
Arrays.sort(reserve);
//데이터 전처리를 해야한다.
//lost와 reserve에 동일한 숫자가 있으면 제거
for(int i=0; i<lost.length; i++){
for(int j=0; j<reserve.length; j++){
if(lost[i] == reserve[j] && reserve[j] != -1){
lost[i] = -1;
reserve[j] = -1;
finalLost--;
break;
}
}
}
//도난 학생들 for 앞뒤자신 번호 비교해서 빌려 받을 수 있으면 lost.length에서 뺀다
//return은 n - final lost로
int front = 0;
int back = 0;
for(int lostNumber : lost){
for(int i=0; i<reserve.length; i++){
if(lostNumber != -1 && reserve[i] != -1 && finalLost >= 0){
front = lostNumber - 1;
back = lostNumber + 1;
if(reserve[i] == front
|| reserve[i] == back){
reserve[i] = -1;
finalLost--;
break;
}
}
}
}
//경우의 수가 1개 더 있음
//서로 겹치게 받을 수 있는 경우 한명이 다른 선택지가 있다면 그걸 선택하면 모두 참여 가능
return n - finalLost;
}
}
분석
몇몇 테스트가 통과되지 않았는데 배열이 sort 되지 않은 것이 문제였음
순간 순간 최선의 선택을 하는걸 그리디 알고리즘이라고 한다.
이 문제에서는 전처리로 같은 숫자를 제거하는 것부터 하고 정렬 후 앞뒤 비교를 해야 정답에 도달할 수 있다.
최적 정답
O(N)으로 해결함. 분석
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;
}
}