[leetcode] 179, 189, 412

412. Fizz Buzz

https://leetcode.com/problems/fizz-buzz/

My Answer 1: Accepted (Runtime: 32 ms - 98.92% / Memory Usage: 15.1 MB - 67.35%)

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        ans = []
        
        for i in range(n):
            if (i+1) % 15 == 0:
                ans.append("FizzBuzz")
            elif (i+1) % 3 == 0:
                ans.append("Fizz")
            elif (i+1) % 5 == 0:
                ans.append("Buzz")
            else:
                ans.append(str(i+1))
        
        return ans

문제 고대로

15 의 배수면 "FizzBuzz"
3 의 배수면 "Fizz"
5 의 배수면 "Buzz"

나머지는 숫자 그대로 넣어주기

---

179. Largest Number

https://leetcode.com/problems/largest-number/

My Answer 1: Wrong Answer (205 / 229 test cases passed.)

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        for i in range(len(nums)):
            nums[i] = str(nums[i])
            
        nums.sort()
        
        for i in range(1, len(nums)):
            if nums[i-1] + "0" == nums[i]:
                nums[i-1], nums[i] = nums[i], nums[i-1]
            
        ans = ""
        for i in range(len(nums)-1,-1,-1):
            a = ans + str(nums[i])
            b = str(nums[i]) + ans
            
            if a > b:
                ans = a
            else:
                ans = b
        
        ans = ans.lstrip('0')
        
        return ans

nums 를 string 으로 바꾸고 정렬한 후,
맨 끝에 0 이 붙는 애들 처리
=> 시작 숫자가 같은 애들 중에 0 붙은 애가 있으면 젤 앞으로 오게 됨
ex) 3, 30, 34 => 30, 3, 34

nums 를 거꾸로 보면서 ans 의 앞, 뒤에 nums[i] 를 붙여보고
그 중에 큰 숫자로 ans update

앞부분에 0 이 붙으면 없애줌

824, 8247 의 경우)
824+8247 이 되어야 하는데
큰 값부터 ans 랑 비교하다 보니 8247+824 가 됨

Solution 1: Accepted (Runtime: 36 ms - 81.89% / Memory Usage: 14.4 MB - 31.76%)

class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
        return '0' if largest_num[0] == '0' else largest_num

LargerNumKey 를 기준으로 nums 를 정렬 (string 으로 변환)

시작 값이 0 이면 return "0"
아니면 return largest_num

복잡하지만 핵심은 어떤 정렬이든 x+y > y+x 를 기준으로 해야한다는 것!!

참고: https://leetcode.com/problems/largest-number/discuss/53298/Python-different-solutions-(bubble-insertion-selection-merge-quick-sorts).

---

189. Rotate Array

https://leetcode.com/problems/rotate-array/

My Answer 1: Accepted (Runtime: 204 ms - 94.33% / Memory Usage: 25.7 MB - 13.49%)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k]

k 는 nums 의 길이로 나눈 나머지로 변경 => rotate 니까

뒤에서부터 k 개를 기준으로 slicing

추가 space 써서 복사하는 방법도 생각해보고
i 와 len(nums)-k+i 를 swap 하고 그 사이에 있던 애들은 맨 뒤로 보내는 방법도 생각해봤는데...
뭔가 찝찝...

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

라고 했기 때문에 3 가지 루션이를 가져옴~

Using Extra Array

Solution 1: Accepted (untime: 60 ms - 78.58% / Memory Usage: 15.5 MB - 62.36%)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        a = [0] * n
        for i in range(n):
            a[(i + k) % n] = nums[i]
            
        nums[:] = a

a 라는 리스트를 만듦
a[(i + k) % n] => rotate 후의 자리부터 숫자를 채워줌

nums 에 복사

O(n)

Using Cyclic Replacements

Solution 2: Accepted (Runtime: 60 ms - 78.58% / Memory Usage: 15.7 MB - 34.84%)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        
        start = count = 0
        while count < n:
            current, prev = start, nums[start]
            while True:
                next_idx = (current + k) % n
                nums[next_idx], prev = prev, nums[next_idx]
                current = next_idx
                count += 1
                
                if start == current:
                    break
            start += 1

next_idx 를 사용하는데... 잘 이해가 안되네요...^^

O(1)

Using Reverse

Solution 3: Accepted (Runtime: 60 ms - 78.58% / Memory Usage: 15.5 MB - 86.08%)

class Solution:
    def reverse(self, nums: list, start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start + 1, end - 1
                
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n

        self.reverse(nums, 0, n - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, n - 1)

이건 리버스를 이용한 천재같은 방식

nums = [1, 2, 3, 4, 5, 6, 7], k = 3

1. 전체 reverse
   => [7, 6, 5, 4, 3, 2, 1]

2. 0 ~ k-1 까지 reverse
   => [5, 6, 7, 4, 3, 2, 1]

3. k ~ n-1 까지 reverse
   => [5, 6, 7, 1, 2, 3, 4]

알아두자!!!

O(1)