Min Rewards 문제풀이

scores 배열안에 [8, 4, 2, 1, 3, 6, 7 ,9, 5] 라는 숫자들이 주어진다. 

이 숫자들을 각각의 순위대로 나열하는 문제이다. 

따라서, [8, 4, 2, 1, 3, 6, 7 ,9, 5]  의 점수 배열이 [4, 3, 2, 1, 2, 3, 4, 5, 1]으로 변화된다.

 

과정

 

8은 4 보다 크다. 

4는 2 보다 크다.

2는 1 보다 크다.

따라서, 순위를 정하면 8 -> 4, 4-> 3, 2-> 2, 1-> 1으로 변화될 수 있다. [ 4, 3, 2, 1 ....]

3은 1보다 크다.

6은 3보다 크다.

7은 6보다 크다.

9는 7 보다 크다.

따라서, 위와같이 순위를 정하면 [4,3,2,1, 2, 3, 4, 5 ...] 이 된다.

마지막으로 5는 9보다 작으므로 [4,3,2,1, 2, 3, 4, 5, 1] 이 된다.

 

코드 

 이 문제는 O(N) time, O(N) sapce 으로 풀 수 있다. 한번의 for loop을 사용함으로써 모든 element를 조회하고 각 element의 상황이 되는 로직을 넣어서 원하는 값을 출력한다.

 

def minRewards(scores):
    # Write your code here.
	cache = [ 1 for _ in scores ]
	
	for i in range(1,len(scores)):
		prev = scores[i-1]
		current = scores[i]
		if current > prev:
			cache[i] = cache[i-1] + 1
	
	for i in range(len(scores)-1,0,-1):
		left = scores[i-1]
		right = scores[i]
		if left > right and cache[i-1] <= cache[i]:
			cache[i-1] = cache[i]+1
	return sum(cache)