[Mock] Microsoft 7

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

My Answer 1: Accepted (Runtime: 28 ms - 90.57% / Memory Usage: 14.3 MB)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()

제 첫번째 사랑... 젤 먼저 떠오른거 RG...^^? 젤 빠르다는 점~~

My Answer 2: Accepted (Runtime: 36 ms - 38.22% / Memory Usage: 14.3 MB - 44.10%)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = collections.Counter(nums)
        scount = sorted(count.items())
        
        i = 0
        for k, v in scount:
            for j in range(i, i+v):
                nums[j] = k
            i += v

제 두번째 사랑 Counter 를 써서 0,1,2 개수만큼 nums 에 순서대로 채워줬읍니다

My Answer 3: Accepted (Runtime: 36 ms - 38.22% / Memory Usage: 14.4 MB - 10.86%)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        start = 0
        end = len(nums)-1
        i = 0
        while i < len(nums) and start < end:
            if nums[i] == 0:
                for j in range(i, start, -1):
                    nums[j] = nums[j-1]
                if i >= start:
                    nums[start] = 0
                    start += 1
                    i -= 1
            elif nums[i] == 2:
                for j in range(i, end):
                    nums[j] = nums[j+1]
                if i <= end:
                    nums[end] = 2
                    end -= 1
                    i -= 1
            i += 1

medium 답게 풀어보자 해서 도전

start, end 를 잡아서

nums[i] 가 0 일때는 i 부터 왼쪽으로 가면서 앞에 값들을 한칸씩 뒤로 옮겨주고 nums[start] = 0
nums[i] 가 2 일때는 i 부터 오른쪽으로 가면서 뒤에 값들을 한칸씩 앞으로 옮겨주고 nums[end] = 2
nums[i] 가 1 일때는 냅둠

---

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

My Answer 1: Time Limit Exceeded (22 / 33 test cases passed.)

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        def func(num, n):
            if len(n) == self.length and int(n) < self.minimum:
                self.minimum = int(n)
            
            for i in range(len(num)):
                func(num[i+1:], n+num[i])
        
        self.length = len(num) - k
        if self.length == 0:
            return "0"
            
        self.minimum = float('inf')
        func(num, "")
        
        return str(self.minimum)

재귀로 숫자마다 조합을 찾아서 길이가 len(num) - k 일때 최솟값 update 해줌