[Leetcode][Python3] 135. Candy

문제 유형: 그리디

 

문제 링크 : https://leetcode.com/problems/candy/

Candy - LeetCode

 

이 문제에 대해서는 할 말이 많다. 바로 배열을 딱 하나만 쓰려는 도전 때문이다.

학교 과제로 이 문제를 풀었는데, 공간복잡도를 줄이면 Bonus Credit를 주는 줄 알고 열심히 풀었다.

나름 고민의 과정이 가치 있었다고 생각하기에 공유하고자 한다.

 

특히 코드를 보면 돌아가기는 하는데 매우 지저분하게 짜여 있다. 일반화를 잘 못해서 끝 부분 처리에 실패했다.

그래도 돌렸을 당시 런타임은 상위 0.5%, 메모리는 상위 25.5% 니까 이를 위안으로 삼겠다.

 

문제 해설 

상황을 바꿔서 비유하겠다. 당신은 공장 사장! 직원들의 스탯은 각기 다르다. 스탯이 높은 직원은 더 많은 돈을 받고 싶어한다.

직원들은 일렬로 서서 일을 하는데, 스탯이 이웃 직원보다 높은 직원은 더 많은 돈을 받으려고 한다. 모든 직원은 기본 시급으로 1000원을 받고, 시급이 올라가는 단위는 1000원이다. 이때 당신이 총 직원의 시급을 최소화하려면 어떻게 해야 할까? 같은 문제다.

 

예를 들면 

[12, 4, 3, 11,34, 34,36, 1,67] 이렇게 어레이가 있다고 하자. 각 항목은 직원의 스탯이다. 

[ 3 , 2, 1, 2, 3, 1, 2, 1, 2] 그렇다면 이렇게 돈을 주는 게 제일 돈을 적게 주면서도, 직원의 불만사항을 충족한다 ( 1 = 1000원이라고 생각해주세요)

 

만약 저 어레이에서 저렇게 돈을 주는 경우가 왜 최소인지 이해가 가지 않는다면 직접 해보자. 

 

풀이(공간복잡도 O(n), 복제 어레이 안씀)

공간복잡도 O(n)으로 푸는 전략은 배열을 처음부터 끝까지 한 번 훑으면 답이 나와야 한다.

따라서 원본 어레이 하나, 총 스코어를 리턴하는 값 이렇게 두 개를 들고가면 된다. 

 

문제를 어떻게 접근해야 할까? 바로 직각삼각형 블록 쌓기를 생각하면 된다.

위 어레이에서 증가하는지, 감소하는지, 일정한 지 화살표를 그려 보자.

그러면 세 가지 지점이 존재한다.

1. 평평한 지점

2. 내려갔다가 올라가는 지점

3. 올라갔다가 내려가는 지점

여기서 '내려갔다가 올라가는 지점'에 해당하는 직원한테는 1000원을 준다. 왜냐고? 내 주변 사람들이 다 나보다 일을 잘하니까. 

그러면 다음과 같은 그림이 그려진다. 거의 정답으로 제시했던 솔루션과 비슷하지 않는가? 여기서 우선 우리가 생각할 수 있는 것은

 

-> 앞, 뒤의 직원이 스탯이 같은 경우, 시급 처리를 어떻게 하지? 다.

답은, 같은 경우에는 직원의 불만 사항이 적용되지 않는다는 점으로부터 알 수 있다. 만약 서로 스탯이 같으면 얼마를 받든 상관하지 않는다. 그래서 직원이 세 명 껴있으면 무조건 가운데 있는 직원한테는 1000원 주면 된다. 만약에 1,2,2,2,3 순서대로 직원이 배치되었다고 하자.

스탯 1 직원에게는 1000원, 2 직원에게는 2000원을 줘야 한다. 그러면 두번째 세번째 직원에게는 그냥 1000원만 줘도 된다. 그리고 스탯 3 직원에게 2000원. 아주 그리디하죠?

따라서 저기 빨간색으로 동그라미 친 부분은, 1원을 주면 된다. 짠! 정답이랑 같지요?

 

그런데 한가지 더 생각할 거리가 있다. 가장 낮은 지점, 그러니까 내려갔다 올라가는 지점을 1로 정하는 데에는 이견이 없다. 왜냐하면 그래야 최소일 거니까. 우리는 내려갔다 올라가는 지점-그리고 올라갔다가 내려가기 시작하는 지점의 길이를 재면 된다. 자연수의 합 공식을 써서 길이 n이면 n*(n+1)/2 하면 되니까. 위에 예제처럼 21, 4, 3 은 길이가 3이다. 그러면 1 +2 + 3, 총 세명에게는 6000원의 시급을 주면 된다. 여기서 잠깐!  올라갔다 내려가는 지점은 어떻게 할까? 예를 들면 [1, 2, 3, 5, 4, 2 ]에서 5를 4 ,2쪽에 넣어야 할까? 아니면 1,2,3 쪽에 넣어야 할까?

이렇게 경계에 있을 때, 그 끄트머리 지점을 왼쪽에 포함시키면 왼쪽 직각삼각형은 길이가 n+1이고 오른쪽은 k다. 오른쪽에 포함시키면 n, k+1이다. 그러면 어디에 포함시켜야 할까? 답은 더 길이가 적은 쪽이다. 왜냐하면 우리는 그리디하니까. 사장은 시급을 더 적게 주고 싶다. :)

 

그래서 (1) 같은 경우, (2) 내려갔다 올라가는 경우, (3) 올라갔다 내려가는 경우 이 세가지를 모두 다 따져서 각 삼각형의 길이를 재고 자연수의 합공식을 써서 더하면 답이 나온다.

코드

class Solution:
    def candy(self, List) :
        profit = 0

        length = len(List)
        inc_num = 0
        dec_num = 0

        inc_flag = 0
        dec_flag = 0

        same_flag = 0

        for i in range(length-1):
        # 값 부여
            if List[i] < List[i+1] :
                if inc_flag != 1:
                    inc_num = inc_num+1

                if dec_num != 0 :

                    dec_flag = 1

            elif List[i] == List[i+1] : #같을 경우 구별

                if (List[i] == List[i+1] and i == 0) or (List[i] == List[i+1] and List[i] == List[i-1])  :
                    profit = profit + 1

                    continue
                elif dec_num != 0: #만약 감소하고 있는 중이었다면 감소를 중지

                    dec_flag = 1
                    profit = profit + 1
                    same_flag = 1
                elif inc_num !=0: #만약 증가하고 있던 중이었다면 증가를 중지

                    inc_flag = 1
                    same_flag = 1


            else :
                dec_num = dec_num +1

                if inc_num !=0 :

                    inc_flag = 1

        #연산 수행
            if inc_flag == 1 and ((dec_flag == 1) or (same_flag == 1) or ((i == length -2) and (List[i+1]< List[i]))):

                if (inc_num) >= (dec_num):
                #증가하는 횟수보다 감소하는 횟수가 적다 -> 감소의 블럭 수는 유지, 증가를 +1로 함.
                    inc_num = inc_num +1
                    dec_num = dec_num -1


                profit = profit + inc_num * (inc_num + 1) / 2
                inc_flag = 0

                if ((i == length -2) and (List[i+1]< List[i])) :
                    dec_num = dec_num + 1
                inc_num = 1


            if dec_flag == 1 :
                dec_num = dec_num +1

                value = dec_num * (dec_num + 1) / 2 - 1
                profit = profit + value

                dec_num = 0
                dec_flag = 0


            if same_flag == 1:

                inc_num = 0
                dec_num = 0
                dec_flag = 0
                same_flag = 0
                continue #초기화


        if inc_num != 0 and dec_num == 0:
            inc_num= inc_num +1
            profit = profit + inc_num * (inc_num + 1) / 2
        elif dec_num != 0 and inc_num!= 0:
            profit = profit + dec_num * (dec_num + 1) / 2
        elif dec_num != 0 and inc_num == 0:
            dec_num = dec_num + 1
            profit = profit + dec_num * (dec_num + 1) / 2
        elif List[length-2] == List[length-1] :
            profit = profit + 1

        profit = int(profit)
        return profit

 

코드가 많이 복잡하다. flag 등으로 상태 표기를 한 점과 끝값 처리가 복잡하다. 이후 수정할 계획이다.