#4 Greedy

해커랭크의 Greedy는 대부분이 Sorting이 핵심이다.

 

1) Minimum Absoulte Difference in an array

주어진 array에서 두개의 숫자 쌍 차이의 절댓값중에서 가장 작은애를 뽑아내는 문제.

sorting을 먼저 해야한다. 그리고 각 인접끼리 빼주면서 최소값을 뽑아내면 된다.

 

2) Luck Balance

질때마다 luck balance가 올라가는데, 이겨야하는 대회가 있고 져도 되는 대회가 있다.

그래서 져도 되는 대회는 무조건 다 지고, 이겨야하는 대회는 최소한으로만 이긴다.

이겨야 하는 대회는 luck balance대로 sorting을 해주고, 이길만큼만 이긴다.

 

3) Greedy Florist

이건 문제 이해가 도저히 안돼서 GG. 문제를 이해하려고 하는데만 1시간썼다.

Discussion board에도 욕이 난무한다.

 

4) Max Min

주어진 array에서 k개만큼 subarray를 뽑았을 때, max(subarray)-min(subarray)가 최소가 되는 집합을 찾아야 한다.

이것도 sorting이 기본이다. sorting을 한 후에 처음부터 k개까지 범위를 지정해놓고, 최소는 [start] 최대는 [start+k]가 될것이므로 배열을 순회하면서 이 두개의 차이가 가장 작은 value를 찾으면 된다. 중간값은 신경쓸필요없다. Greedy니까.