[프로그래머스] 체육복 / java, Greedy

https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

 

레벨1 이지만, 문제 안에 뭔가 신경쓸게 많았던 문제.! 

- 훔친 당한 학생이 여벌의 체육복을 가지고 있다면, 그 학생은 자신의 여벌 체육복을 입어야한다! 

- 훔친 학생의 수보다 여벌의 체육복을 가져온 수가 더 많을수도 있다.

 

 

나의 경우,

해당 문제를 재귀 or 완전탐색으로 풀어볼까 고민했다.. (?)

• 재귀로 풀면 안되는 이유, lost[0], lost[2] ... 의 데이터값이 있을때 lost[0]이 원하는 체육복 값을 찾지 못할 수도 있는데 
• 만약 원하는 체육복을 찾지 못하면 그 뒤의 lost[2] (index=2)의 함수로 넘어가지 못한다!! 
• 해당 부분때문에 고민하느라 조금 시간 걸렸다.

아래는 잘못된 재귀로 푼 코드입니다 !!!! 참고 ❌❌❌❌ 

 

 

그리디 알고리즘이란, 

탐욕법(탐욕 알고리즘, Greedy Algorithms)
- 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법.
- 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘.

- 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

- 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

- 그 순간의 답이 최적이라 생각하고 ( greedy, 탐욕스럽게- 미래를 생각하지않고. 그 순간만 바라봄! ), 각 단계에서 최선을 선택하여 진행하는 방법!

 

 

✅ 위의 문제가 그리디 알고리즘으로 풀어야 하는 이유!

-  체육복을 잃어버린 학생은-> 자신의 숫자보다 작거나 큰 체육복을 선택해야되는데, 자기보다 작은 숫자를 먼저 선택하는것이 최선이다!

    ? 자기보다 혹시라도 큰 숫자를 선택하면, 그 뒤의 학생이 선택을 못할 수도 있다.

ex.  체육복 잃어버린 학생 = 2,4

       여벌의 체육복 = 1,3 

- 체육복 잃어버린 2의 학생이 1이 아닌 3을 고르면? 4의 학생은 빌릴 체육복이 없다 ! 

-> 그러니, 자기보다 1작은 수의 체육복이 있다면 그것을 고르는것이 최선이고, 없다면 자기보다 1 큰 체육복을 골라야 함

 

 

* 여기서는 신경써줘야할 점은, 여벌체육복을 가져온 학생이 도난당한 경우를 제외 시켜줘야한다.* 도난당한 학생에게 체육복을 빌려주는 경우에 break문을 쓴 이유는? -> 자기보다  -1 작은 체육복도 있고, 1 큰 체육복 둘다 존재하면 작은 체육복을 선택후 빠져나가야하기 때문.