[Programmers] 체육복 - 탐욕법 (Greedy)

import java.util.ArrayList;
import java.util.LinkedHashSet;

// 체육복 - 탐욕법 (Greedy)
public class Uniform {

	// Greedy 알고리즘 X
	public int solution1(int n, int[] lost, int[] reserve) {
		
		ArrayList<Integer> lostList = new ArrayList<Integer>();
		LinkedHashSet<Integer> solutionSet = new LinkedHashSet<Integer>(); // Set은 list와 같으나 중복 키를 허용하지 않는다. 해결한 학생을 저장하기 위해 Set 선언
		// LinkedHashSet은 add()한 순서대로 저장, HashSet은 임의의 순서로 저장, TreeSet은 자연적 순서대로 저장

		for(int ele : lost) { // lost 배열을 lostList에 저장
			lostList.add(ele);
		}

		for (int i = 0; i < lost.length; i++) {
			for (int j = 0; j < reserve.length; j++) {

				if (lost[i] == reserve[j]) {
					solutionSet.add(lost[i]); // Set에는 해결한 학생을 저장
					reserve[j] = lost[i] = -1; // 해결된 학생은 -1로 바꾸어 줌
				}
			}
		}

		for (int i = 0; i < lost.length; i++) {
			for (int j = 0; j < reserve.length; j++) {

				if (lost[i] == reserve[j] - 1) {
					solutionSet.add(lost[i]);
					reserve[j] = lost[i] = -1; // 해결된 학생은 -1로 바꾸어 줌
				}

				if (lost[i] == reserve[j] + 1) {
					solutionSet.add(lost[i]);
					reserve[j] = lost[i] = -1; // 해결된 학생은 -1로 바꾸어 줌
				}

			}
		}

		lostList.removeAll(solutionSet); // removeAll() : 겹치는 원소 모두 삭제. retainAll() 메소드는 겹치는 원소를 남기고 나머지 원소 삭제. lost학생을 저장한 list에서 해결한학생(set)을 제거
		return n - lostList.size(); // 전체 학생 수에서 해결하지 못한 학생 수를  뺀 값을 리턴 
	}

	
	// Greedy 알고리즘 O
	public int solution(int n, int[] lost, int[] reserve) {

		int answer = n - lost.length;
		LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
		
		for (int ele : reserve) {
			set.add(ele);
		}

		for (int i = 0; i < lost.length; i++) {

			if (set.contains(lost[i])) {
				set.remove(lost[i]);
				answer++;
				lost[i] = -1;
			}
		}

		for (int i = 0; i < lost.length; i++) {
			if (set.contains(lost[i] - 1)) {
				set.remove(lost[i] - 1);
				answer++;
				lost[i] = -1;
			} else if (set.contains(lost[i] + 1)) {
				set.remove(lost[i] + 1);
				answer++;
				lost[i] = -1;
			}
		}

		return answer;
	}

	public static void main(String[] args) {

		Uniform u = new Uniform();

		int[] lost1 = { 2, 4 };
		int[] reserve1 = { 1, 3, 5 };

		int[] lost2 = { 2, 4 };
		int[] reserve2 = { 3 };

		int[] lost3 = { 3 };
		int[] reserve3 = { 1 };

		int[] lost4 = { 2, 4 };
		int[] reserve4 = { 4 };

		int[] lost5 = { 4, 5 };
		int[] reserve5 = { 4 };

		int[] lost6 = { 1, 4, 5 };
		int[] reserve6 = { 4 };

		int[] lost7 = { 1, 4, 5 };
		int[] reserve7 = { 2, 4 };

		int[] lost8 = {};
		int[] reserve8 = { 2, 4 };

		int[] lost9 = { 1, 3, 4, 5 };
		int[] reserve9 = { 2, 4 };

		int[] lost10 = { 4, 5, 6, 7, 9 };
		int[] reserve10 = { 3, 4, 5, 6, 8, 9 };

		int[] lost11 = { 1, 3 };
		int[] reserve11 = { 1, 2 };

		System.out.println(u.solution(5, lost1, reserve1)); // 5
		System.out.println(u.solution(5, lost2, reserve2)); // 4
		System.out.println(u.solution(3, lost3, reserve3)); // 2
		System.out.println(u.solution(5, lost4, reserve4)); // 4
		System.out.println(u.solution(5, lost5, reserve5)); // 4
		System.out.println(u.solution(5, lost6, reserve6)); // 3
		System.out.println(u.solution(5, lost7, reserve7)); // 4
		System.out.println(u.solution(5, lost8, reserve8)); // 5
		System.out.println(u.solution(5, lost9, reserve9)); // 3
		System.out.println(u.solution(30, lost10, reserve10)); // 30
		System.out.println(u.solution(5, lost11, reserve11)); // 5

	}

}

• Dynamic Programming VS Greedy Algorithm : https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5

• Greedy Algorithm
  https://ratsgo.github.io/data%20structure&algorithm/2017/11/22/greedy/

• Dynamic Programming
  https://ratsgo.github.io/data%20structure&algorithm/2017/11/15/dynamic/