[JAVA] 탐욕법(Greedy) "체육복"

 

필자는 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이상..?)