그냥 이중for문 돌려서 lost랑 reserve-1, reserve+1인거 겹친거 빼가면서 answer++해주면 될거라 생각했다. 그런데 반례를 생각하지 못했다. lost사람이랑 reserve사람이랑 겹칠경우가 있을 수 있었다.
import java.io.*;
import java.util.*;
class 체육복 {
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<reserve.length;i++){
for(int j=0;j<lost.length;j++){
if(reserve[i]-1==lost[j] || reserve[i]+1==lost[j]){
answer++;
lost[j]=-100;
reserve[i]=-200;
}
}
}
return answer;
}
}
반례 ...
그래서 lost와 reserve에서 겹치는 수 먼저 빼줘야한다.
import java.io.*;
import java.util.*;
class 체육복 {
public int solution(int n, int[] lost, int[] reserve) {
int answer = n-lost.length;
Arrays.sort(lost);
Arrays.sort(reserve);
//반례(도난당한사람이랑 여분있는사람이 같을때)
//예 n=5, lost[2,3], reserve[1,2]
for(int i=0;i<reserve.length;i++){
for(int j=0;j<lost.length;j++){
if(reserve[i]==lost[j]){
answer++;
reserve[i]=-200;
lost[j]=-100;
}
}
}
for(int i=0;i<reserve.length;i++){
for(int j=0;j<lost.length;j++){
if(reserve[i]-1==lost[j] || reserve[i]+1==lost[j]){
answer++;
lost[j]=-100;
reserve[i]=-200;
}
}
}
return answer;
}
}
그리디는 항상 까다롭다...
맨날 탐색 문제만 풀다가 이런 문제 만나면 당혹..
연습해야겠다