Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/equal/problem?isFullScreen=true
문제의 제약 조건은 다음과 같이 두 가지가 있었다. - "한 명을 제외하고 초콜릿을 나눠줄 수 있다." - "결과적으로 배분한 초콜릿의 개수가 같아야 연산이 끝이 난다."
문제를 풀어나가는 아이데이션 과정부터 쉽지 않았다. 특히 첫번째 조건을 코드로 처리하는 데 있어서 어려움을 겪었다. 오직 딱 한 명을 제외하고 숫자를 더해서(1,2,5) 모든 Array의 숫자들을 동일하게 만드는 것이 어려웠다.
구글링을 통해 문제를 해결해 나갈 수 있었는데, 먼저 1번 제약 조건을 뒤집어서 생각하는 것이 문제 해결의 시작이었다. - 즉, 초콜릿을 한 명만 제외하고 나눠줘서 동일한 초콜릿으로 만드는 문제를 초콜릿을 한 명의 것을 빼앗는 것으로 뒤집어 생각하는 방식이다. 우리가 구하고자 하는 값은 최소 연산의 수이므로 가능한 접근 방식이다. 다음의 그림처럼, [2,2,3,7] 의 Array에서 index3을 제외하고 +5하는 문제는 index3의 값을 -5하는 문제로 바뀔 수 있다. 하나의 원소의 값을 특정값(1,2,5)을 빼는 방식으로 연산하는 것이 생각하기가 더 쉬운 접근법이기도 하다.
- 1,2,5를 빼서 4개의 원소를 동일하게 만드는 방식으로는 다음의 점화식을 사용할 수 있다.
x = x//5 + (x%5)//2 + (x%5)%2 (5의 몫) (그 외의 2의 몫) (그 외의 1의 몫)
다만, 최소값을 Array의 최소값이 아닌 Array의 최소값 +1, +2, +3, +4의 후보군을 만들어서 최종 최소값을 산출할 수 있다.
def equal(arr):
m = min(arr)
t = [0]*5
for i in arr:
for j in range(5):
x = i-(m-j)
#print("i",i, "j",j,"x",x)
x = x//5 +(x%5)//2 + (x%5)%2
t[j]+=x
#print(t)
return min(t)