LeetCode 1578.

dombe·2022년 10월 3일
0

Coding Test(Python)

목록 보기
35/45

문제 링크

잡담.

  1. 오늘이 개천절인지 모르고 있었다..

  2. 리트코드는 백준에 비해 배려가 넘치는 사이트 같다는 생각이 든다.(물론 최상위 난이도 문제는 없는 것 같지만..) 풀이를 제출했을 때 틀린, 혹은 시간초과가 난 케이스에 대해 그 예시를 그대로 보여주는 덕분에 이 코드를 검토할 때 이왜틀?이 거의 없는 편이다.

문제 설명.

string colorscolor와 길이가 같은 list neededTime이 주어진다.
colors에 적힌 것은 소문자들의 나열로 한 줄로 이어져있는 연속된 풍선들의 색깔을 나타낸다. neededTime의 원소에는 각 위치의 풍선을 때는데 드는 비용이다.

문제의 목표는 최소의 시간 비용을 들이면서, 한줄로 이어져있는 연속된 풍선들의 색깔이 서로 연속되지 않게 만드는 것이다.

예시를 들어보자.
colorsabcaab라고 할 때 목표는 이 풍선들의 색깔이 abcab가 되게 만드는 것이고, 결과적으로 4번째 혹은 5번째 풍선을 제거하면 된다.
만약 neededTime == [1,3,5,7,6,4] 라고 가정하면 abcab를 만들기 위해 7 혹은 6의 비용이 들기 때문에 6을 출력해주면 된다.

풀이방법.

별다른 좋은 아이디어가 떠오르지 않아 초기 결과 result를 0으로 두고, 배열을 돌며 같은 색이 2개 이상 붙어있을 때 연속된 비용의 합에 최대 값을 빼준 값을 result에 더해주는 방식으로 코드를 돌렸다.

그리하여

초기 코드

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        leng = len(colors)
        conse_lst = []
        curr = colors[0]
        tmp = []
        for i in range(leng):
            if colors[i] != curr:
                curr = colors[i]
                conse_lst.append(tmp)
                tmp = [i]
            else:
                tmp.append(i)
        
        if tmp:
            conse_lst.append(tmp)
        
        result = 0
        for i in conse_lst:
            if len(i) == 1:
                continue
                
            maxi = 0
            subt = 0
            for j in i:
                subt += neededTime[j]
                if neededTime[j]>maxi:
                    maxi = neededTime[j]
            
            result += subt-maxi
            
        return result

그런데 효율이 아무래도 너무 안습이라 뺄 것을 빼면서 좀 더 개선을 했다.

그리고 그 결과

최종 제출

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        leng = len(colors)
        curr = colors[0]
        start = 0
        result = 0
        
        for i in range(1,leng):
            if colors[i] != curr:
                curr = colors[i]
                result += sum(neededTime[start:i])-max(neededTime[start:i])
                start = i
        
        if start != i:
            result += sum(neededTime[start:leng])-max(neededTime[start:leng])
        
        return result

뭐 이것저것 제거해서 Runtime은 기존의 반(3110ms --> 1568ms, 70.78%)으로, 메모리는 약 12% 정도(28.7mb --> 25.1mb, 12.42%)로 줄였다. 메모리를 보았을 때 더 효율적인 방법이 있는 것 같긴 한데 이쯤만 해도 나쁘지 않다고 생각되서 더이상의 코드 개선은 stop!(메모리를 건드릴 요소가 아마도 result가 결과적으로 엄청 큰 수가 되고, 매우 잦은 변화가 있을 때 뿐일 것 같은데 그런 케이스가 있나보다.)

profile
다양한 분야에 관심이 많은 초보 개발자 입니다.

0개의 댓글