HackerRank Interview Preparation Kit > Greedy

HackerRank의 Interview Preparation Kit > Greedy의 Medium 이상 문제

Greedy Florist - medium

문제요약

n개의 꽃 가격 c와 k명의 사람이 있을 때, 꽃의 가격은 동일한 사람이 꽃을 사면 꽃 가격에 이전 구매 횟수의 배수로 가격이 측정될 때 전체 꽃을 사는 최소 값을 계산(즉 꽃 가격이 [2, 3]이고 한 사람이 꽃을 사면 처음엔 3, 두 번째는 2*2로 전체 가격은 7에 살 수 있다. 순서가 바뀌면 2 + 3*2 = 8이 되므로 최소는 7)

첫 줄엔 n, k. 두번째 줄엔 c (1<=n,k<=100, 1<=c[i]<=10^6, answer<2^31, 0<=i<n)

Sample Input 

3 3

2 5 6

Sample output

13

풀이

횟 수가 늘어날 수록 가격이 배가 되므로 작은 가격의 꽃을 뒤에 사야한다. 즉 큰 수부터 더하면서 사람의 수가 넘어가면 가격에 *반복된 횟수 만큼 계산하면 최소값을 구할 수 있다.

Max Min - medium

문제요약

integer배열 arr에서 k개의 subarr을 선택해서 max(subarr)-min(subarr)의 최소값을 계산

첫 줄에 n, 두번째 줄엔 k, 다음 줄부터 n개의 integer (2<=n<=10^5, 2<=k<=n, 0<=arr[i]<=10^9)

Sample Input

7

3

10

100

300

200

1000

20

30

Sample output

20

풀이

차를 작게 해야 하므로 인접한 수 끼리의 차를 구해야 하고, 따라서 정렬 후에 i+k-1번째 수와 i번째 수의 차의 최소값을 구하면 된다.

Reverse Shuffle Merge - Advanced

문제요약

문자열 A에 대해서 merge(reverse(A), shuffle(A))인 s가 주어지면 가능 A값 중 문자열 순서로 가장 작은 A를 계산

reverse(A) : 순서를 역으로 변환, reverse('abc') = 'cba'

shuffle(A) : 랜덤으로 섞음

merge(A1, A2) : A1과 A2의 각각 등장 순서는 유지하되 랜덤하게 합침, merge('abc', 'def') = 'abcdef' or 'abdcef'...

Sample Input

eggegg

Sample output

egg

풀이

문제 풀이는 비교적 빨리 찾았으나 구현하는데 애먹은 문제

일단 전체 문자의 등장 횟수의 절반씩을 포함하는 substring이 후보가 되고, shuffle은 랜덤이므로 크게 고려하지 않아도 가능. reverse한 string이 s에 포함되어 있어야 하고 원래의 string이 최소여야 하므로, s를 뒤집어서 s에서 등장횟수(절반)를 만족하는 최소의 부분 수열을 찾아내면 된다.

즉 s가 'abcdefgabcdefg'이면 a부터 g까지 각 2개씩이므로 reverse한 'gfedcbagfedcba'에서 a~g까지 하나씩 등장하는 최소 수열을 찾으면 'agfedcb'가 정답

구현은 전체 갯수와 절반의 갯수를 미리 계산해 놓은다음,

reverse한 string 앞부터 전체 갯수에서 지나간 문자의 갯수를 하나씩 줄이고(현재 이후로 남은 문자 수), 이 수가 절반 갯수를 만족할 때까지(현재 문자를 선택가능) 진행하면서 가장 작은 문자를 선택. 선택 후 절반 갯수에서 해당 문자 수를 하나 줄이고 다음 선택된 다음 문자부터 다시 반복. (Testcase 16은 정답에 오류가 있는 듯.)