[그리디] 체육복 - Java코드

https://programmers.co.kr/learn/courses/30/lessons/42862?language=java 

코딩테스트 연습 - 체육복

 

 

문제

 

 

접근법

전체사람 중, 잃어버린 사람을 제외하고, 그들중, 빌릴 수 있는 경우마다 count해서 정답을 반환해주어야겠다.

 

나는 리스트를 이용하면 빌려준 사람들의 요소를 삭제할수있기 때문에 좋을것같다는 바보같은 생각을 했다.

 

포인트

예제에는 존재하지 않지만, 잃어버린 사람들중 여벌을 가지고 있을수 있다.

그런 경우를 대비하여, 잃어버린 사람중 여벌을 가지고있는 사람들은 빌려줄수없도록 설정해주어야 한다.

예를 들어 n=3 , lost={1,2}, reserve = {2,3} 인 경우,

2번이 자기 자신것만 입는 경우로 생각하고, 제외시켜야 정답인 2를 도출할수 있다.

그렇지 않은 경우, 3이 될 수 있다

 

( 사실 현실세계에서는 내꺼 빌려주고 대충싸이즈 맞는친구꺼 빌려 입을 수 있는거 아닌가? 그게 로직상 최댓값 아닌가) 

 

 

풀이 1

public static int solution(int n, int[] lost, int[] reserve) {
    int[] arr = new int[n+1]; // 0번은 편의상 사용하지 않을거임
    int ans=n;
    for(int l : lost) arr[l]--;
    for(int r : reserve) arr[r]++;
    for (int i = 1; i < arr.length; i++) {
        if(arr[i]==-1) { // 옷을 잃어버린 사람이면 필요한 경우
            if (arr[i-1] == 1) { // 앞사람이 여벌의 옷이 있으면 빌려줌
                arr[i-1]--;
                arr[i]++;
            } else if (i< arr.length -1 && arr[i+1] == 1) { // 뒷사람이 여벌의 옷이 있으면 빌려줌
                arr[i+1]--;
                arr[i]++;
            } else { // 위 두경우에 해당하지 않으면 , 못빌린거임
                ans--;
            }
        }
    }
    return ans;
}

사람의 수 N만큼의 크기를 갖는 배열을 선언하고 (편의상 0번을 사용하지않는 경우 N+1로 선언) 

여벌의 옷을 가진 사람을 1로 없는 사람은 -1로 셋팅한다 (중요 : 여벌의 옷을 도둑맞을수 있기 떄문에 + / - 연산을 해준다)

0번을 사용하지않는 경우, 앞 사람에게 옷을 빌릴 수 있는지부터 체크하면서 계산해주고,

뒷사람에게서 옷을 빌릴수있는지를 체크해준다 ( 이때, 배열 인덱스에 범위를 벗어나지 않도록 &&로 선행조건을 넣어준다)

N명의 사람중에서 도둑맞아서 빌릴수없는 연산으로 사람만큼을 빼주어 결과를 구했다.

 

풀이 2

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i : reserve)  list.add(i);
        int ans = n-lost.length;
        // 잃어버렸지만, 여벌있는 놈들 제거
        for(int i=0;i<lost.length;i++)  {
            if(list.contains(lost[i])){
                for(int j=0;j<list.size();j++) {
                    if(list.get(j)==lost[i]) {
                        list.remove(j);
                        lost[i]=-1;
                        ans++;
                        break;
                    }
                }
            }
        }
        // 잃어버렸지만 빌려주는 경우 count
        for(int i : lost)  {
            for(int j=0;j<list.size();j++) {
                if(list.get(j)<=i+1 && list.get(j)>=i-1) {
                    list.remove(j);
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
}

Collection에 List를 선언하여 대여가 가능한 사람들을 넣어준다.

잃어버렸지만, 여벌이 있는 사람먼저 체크해주면서 list에서 진짜 대여가능한 사람만 남긴다.

빌려줄수 있는 경우만 체크해주면서

옷을 도둑맞은 사람들중 대여받은 사람들을 count해준다.