체육복 - 탐욕법

문제 :

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

 

문제를 푸는데 꽤나 오랜 시간이 걸린 문제다.

나의 해답 

public int solution(int n, int[] lost, int[] reserve) {
		int answer = n - lost.length;

		List<Integer> list = new LinkedList<Integer>();
		for (int lostStd : lost) {
			list.add(lostStd);
		}

		List<Integer> reserveList = new ArrayList<Integer>();
		for (int i : reserve) {
			if (list.indexOf(i) != -1) {
				list.remove(list.indexOf(i));
				answer += 1;
			} else {
				reserveList.add(i);
			}
		}

		for (int i : reserveList) {

			int previousIdx = list.indexOf(i - 1);
			int postIdx = list.indexOf(i + 1);

			boolean isExist = false;
			if (previousIdx != -1) {
				list.remove(previousIdx);
				answer += 1;
				isExist = true;
				continue;
			}

			if (!isExist) {
				if (postIdx != -1) {
					list.remove(postIdx);
					answer += 1;
				}
			}
		}

		return answer;
	}

 

결과 제출시 5번, 7번 문제에 막혀서 애를 먹었던 제출 코드

public int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;

        List<Integer> list = new LinkedList<Integer>();
        for(int lostStd : lost) {
        	list.add(lostStd);
        }
        
        for(int i : reserve) {

        	if(list.indexOf(i) != -1) {
        		list.remove(list.indexOf(i));
        		answer+=1;
        		continue;
        	}
        	
        	int previousIdx = list.indexOf(i-1);
        	int postIdx = list.indexOf(i+1);
        	
        	boolean isExist = false;
        	if(previousIdx != -1) {
        		list.remove(previousIdx);
        		answer+=1;
        		isExist = true;
        		continue;
        	}
        	
        	if(!isExist) {
        		if(postIdx != -1) {
        			list.remove(postIdx);
        			answer+=1;
        		}
        	}
        }
        
        return answer;
    }

-> 이 코드가 틀린 이유는 여벌의 체육복을 가진사람이 도난당한 경우, 자기 자신한테 우선적으로 빌려줘야 해서 체크 할 리스트에서 제거 후 확인을 했어야 하는데, 나는 제거를 우선순위로 하지 않고, 체크하면서 제거 작업을 해서 100%의 정답을 얻지 못했다고 생각한다.