코더들의 실력 평가 점수를 담고 있는 숫자 리스트 ratings가 주어졌다고 가정해 봅시다. 매니저는 모든 코더에게 기본적으로 1000원을 지급하고 싶어 합니다. 단, 두 코더가 서로 인접해 있을 경우에는 실력이 더 좋은 코더에게 반드시 그렇지 못한 코더보다 최소 1000원 이상 더 많이 지급해야 한다는 제약 조건이 있습니다. 우리는 이러한 조건을 모두 만족하면서 매니저가 지급해야 하는 최소 총액을 구하는 프로그램을 작성해야 합니다.
예를 들어 입력이 ratings = [1, 2, 5, 1]이라면 출력은 7000이 됩니다. 각 코더에게 지급할 수 있는 최소 금액이 차례대로 [1000, 2000, 3000, 1000]이기 때문입니다.
문제 해결 접근 방법
이 문제는 두 번의 순회(two-pass) 방식으로 효율적으로 해결할 수 있습니다. 왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번 훑으면서 각 방향의 증감 조건을 처리하는 것입니다. 해결 단계는 다음과 같습니다.
- ratings와 같은 크기의 리스트 pay를 만들고, 모든 값을 1로 초기화합니다. (모든 코더는 최소 1단위를 받습니다.)
- i를 1부터 ratings의 마지막 인덱스까지 순회하며,
ratings[i] > ratings[i-1]인 경우pay[i] = pay[i-1] + 1로 갱신합니다. 이는 왼쪽에서 오른쪽으로 갈수록 성과가 좋아지는 구간을 처리합니다. - 이번에는 i를 마지막에서 두 번째 인덱스부터 0까지 역순으로 순회하며,
ratings[i] > ratings[i+1]인 경우pay[i] = max(pay[i], pay[i+1] + 1)로 갱신합니다. 이는 오른쪽에서 왼쪽으로 갈수록 성과가 좋아지는 구간을 처리하며, 두 방향의 조건을 동시에 만족하도록 기존 값과 비교하여 더 큰 값을 유지합니다. - 마지막으로 pay 리스트의 모든 요소의 합에 1000을 곱한 값을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다. 아래 예시 코드를 통해 자세히 살펴보겠습니다.
구현 예제
class Solution:
def solve(self, ratings):
pay = [1 for _ in ratings]
for i in range(1, len(ratings)):
if ratings[i] > ratings[i-1]:
pay[i] = pay[i-1] + 1
for i in range(len(ratings)-2, -1, -1):
if ratings[i] > ratings[i+1]:
pay[i] = max(pay[i], pay[i+1] + 1)
return sum(pay) * 1000
ob = Solution()
ratings = [1, 2, 5, 1]
print(ob.solve(ratings))
입력
[1, 2, 5, 1]
출력
7000
동작 원리 정리
첫 번째 순회에서는 오름차순 구간을 따라 보상이 점진적으로 증가하도록 만들고, 두 번째 순회에서는 내림차순 구간을 역방향으로 확인하며 이미 계산된 값보다 커야 할 경우에만 값을 올립니다. 이렇게 하면 인접한 모든 코더 쌍에 대해 '성과가 좋은 사람이 최소 1단위 더 많이 받는다'는 조건이 보장되고, 전체 지급액도 최소화됩니다.