필자는 List를 활용하여 알고리즘을 구성했다.
List의 종류에 대해서 공부할 필요성을 느꼈다.
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
//값 넣어놓기
List<Integer> l = new ArrayList<>();
List<Integer> r = new ArrayList<>();
for(int i = 0; i<lost.length; i++)
l.add(lost[i]);
for(int i=0; i <reserve.length; i++)
r.add(reserve[i]);
n= n-lost.length;//5명중 3명 잃어버림. n=2
for(int i=0; i<lost.length; i++){
//잃어버렷지만 여벌옷 있는 학생
if(r.contains(lost[i])&&l.contains(lost[i])){
System.out.println(i);
n++;//1명 있으면 n=3
//(Integer)해야 index값이 아니라 objec로 인식
r.remove((Integer)lost[i]);
l.remove((Integer)lost[i]);
}
else{//lost값 작은것부터 비교
if(r.contains(lost[i]-1)){//작은값있으면
r.remove((Integer)(lost[i]-1));
l.remove((Integer)(lost[i]));
n++;
System.out.println("else 1 : " +i);
}
else if(r.contains(lost[i] +1)){//큰값있으면
if(i+1<lost.length && lost[i+1] == lost[i] +1){
continue;
}
r.remove((Integer)(lost[i]+1));
l.remove((Integer)(lost[i]));
n++;
System.out.println("else 2 : " +i);
}
else{//해당하는값이 없으면 lost에서만 지우고 reserve는 놔둬
l.remove((Integer)lost[i]);
System.out.println("else 3 : " +i);
}
}
}
return answer=n;
}
}
무척 코드가 길게 나왔다.
테스트케이스 12번 오류가 발생했는데, n=8, lost= [4,5] , reverse=[5,6] 인 경우에
lost {4}는 else if 두번째 케이스를 reverse{5}를 이용해 해결하는데, 이 경우 lost{5}를 사전에 reverse{5}로 처리했어야 하는데, reverse{6}으로 처리되므로 n=8이 나온다.(정답 n=7)
위 경우 reverse{5}는 문제의 "체육복 잃어버린사람이자 여분을 가져온사람은 빌려주지 못한다"라는 선조건에 위배된다.
따라서 else if에서 lost[i+1] == lost[i] 값인지 체크를 해서, 같으면 continue로 건너뛴다.
다른사람의 코드가 더 효율적으로 보이니 아래의 코드를 참고하는게 좋다.
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;
}
}
people[]에 들어간 값중
<첫번째 if조건문> -1이 아닌 값들은
위에서 언급하였던 예외사항에 들어가는값도 선처리가 되고, lost에도 포함되지 않는 사람이므로
<두번째 IF/ELSEIF>
if, else if는 i-1과 i+1에 reserve인 값(1인 값&& lost+reserve=0이 아닌값)이 있는 여분을 나누어주는 시행이다.
<두번째 ELSE>
나머지 값들은 나누어줄 수 없는 분실자들이므로 answer--;를 한다.
조건문의 우선순위를 먼저 생각해내는 아이디어와
두개의 배열을 i값과 array[i] 값을 이용하여 하나의 배열로 합쳐내는 방식을 다시 한번 배울필요성을 느꼈다.
이전에, HashSet을 할때 사용한 방식과 비슷한 방식이다(-1, 0, 1이상..?)
'코딩테스트 > Java' 카테고리의 다른 글
[JAVA] 탐욕법(Greedy) "구명보트" (0) | 2020.10.07 |
---|---|
[JAVA] 탐욕법(Greedy) "큰 수 만들기" (0) | 2020.10.05 |
[JAVA] 완전탐색 "소수 찾기" (0) | 2020.09.23 |
[JAVA] 완전탐색 "모의고사" (0) | 2020.09.21 |
[JAVA] 정렬 "가장 큰 수" (0) | 2020.09.18 |