[Mock] Google 6

949. Largest Time for Given Digits

Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

Return the latest 24-hour time in "HH:MM" format. If no valid time can be made, return an empty string.

My Answer 1: Accepted (Runtime: 32 ms - 76.80% / Memory Usage: 14.4 MB - 32.80%)

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        arrDic = collections.Counter(arr)
        
        # 가능한 조합들을 구해줌
        comb = []
        for i in range(len(arr)):
            for j in range(len(arr)):
                tmp = arr[i] * 10 + arr[j]
                if tmp not in comb and tmp < 60 and i != j:
                    comb.append(tmp)
        # 정렬까지~
        comb.sort()
        
        self.result = ""
        
        # 정답을 찾는 부분은 함수로 분리
        def findTime(length):
            # [hour 찾기]
            # length 부터 24 보다 작은 숫자 중에 젤 큰 값 찾기
            for i in range(length,-1,-1):
                if comb[i] < 24:
                    if comb[i] < 10:
                        self.result += "0"
                    self.result += str(comb[i])
                    # 두자리 숫자를 사용했다는 의미로 arrDic 업데이트
                    arrDic[comb[i]//10] -= 1
                    arrDic[comb[i]%10] -= 1
                    break
                    
            # 적절한 hour 가 없으면 빠져나감
            if not self.result:
                self.result = ""
                return

            self.result += ":"
            
            # [minute 찾기]
            # hour 가 사용하지 않은 숫자의 조합 중에 젤 큰 값 찾기
            for i in range(len(comb)-1,-1,-1):
            	# 10 의 자리, 1의 자리 하나하나 사용여부 판단
                if arrDic[comb[i]//10] != 0:
                    arrDic[comb[i]//10] -= 1
                    # 둘 다 안쓴 숫자들이면 답이니까 빠져나감
                    if arrDic[comb[i]%10] != 0:
                        if comb[i] < 10:
                            self.result += "0"
                        self.result += str(comb[i])
                        break
                    # 한자리만 가능 => X, 다시 원상복귀해주고 continue
                    else:
                        arrDic[comb[i]//10] += 1
                        continue
                        
            # 적절한 minute 이 없으면 빠져나감
            if len(self.result) != 5:
                self.result = ""
                return
        
        # hour 부분이 무조건 24 보다 작은 숫자 중에 젤 큰 값이면 안됨
        # arr 의 모든 숫자를 사용하려면 다 따져봐야해서...
        for i in range(len(comb)-1, -1, -1):
            if comb[i] < 24:
                arrDic = collections.Counter(arr)
                findTime(i)
                if len(self.result) == 5:
                    return self.result
                self.result = ""
        
        return self.result

저번에 풀었던 비슷한 문제처럼 조합 구해서 했읍니다

---

307. Range Sum Query - Mutable

Given an array nums and two types of queries where you should update the value of an index in the array, and retrieve the sum of a range in the array.

Implement the NumArray class:

• NumArray(int[] nums) initializes the object with the integer array nums.
• void update(int index, int val) updates the value of nums[index] to be val.
• int sumRange(int left, int right) returns the sum of the subarray nums[left, right] (i.e., nums[left] + nums[left + 1], ..., nums[right]).

My Answer 1: Time Limit Exceeded (9 / 15 test cases passed.)

class NumArray:

    def __init__(self, nums: List[int]):
        self.numarr = nums

    def update(self, index: int, val: int) -> None:
        self.numarr[index] = val

    def sumRange(self, left: int, right: int) -> int:
        result = 0
        
        for i in range(left, right+1):
            result += self.numarr[i]
        
        return result
        
        # 이렇게 쓰면 11 개까진 통과됨..^^
        #return sum(self.numarr[left:right+1])


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)