[Mock] Microsoft 8

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

My Answer 1: Accepted (Runtime: 116 ms - 63.78% / Memory Usage: 15.4 MB)

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # O(1) 과 linear.... 내머리는 너무나 나빠서...
        
        length = len(nums) // 3
        result = set()
        nums.sort()
        
        now = nums[0]
        cnt = 1
        for i in range(1, len(nums)):
            if cnt > length:
                result.add(now)
                
            if nums[i] != now:
                now = nums[i]
                cnt = 1
            else:
                cnt += 1
        
        if cnt > length:
            result.add(now)
        
        return list(result)

정렬한 후, 숫자마다 count 해주면서 length 보다 크면 result 에 넣어줌

숫자가 바뀌면 now 와 cnt 는 초기화

My Answer 2: Accepted (Runtime: 276 ms - 5.30% / Memory Usage: 15.4 MB - 62.81%)

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # O(1) 과 linear.... 내머리는 너무나 나빠서...
        
        length = len(nums) // 3
        nums.sort()
        
        now = nums[0]
        cnt = 1
        i = 0
        while i < len(nums)-1:
            if cnt <= length:
                nums.pop(i)
            else:
                i += 1
                
            if nums[i] != now:
                now = nums[i]
                cnt = 1
            else:
                cnt += 1
        
        if cnt <= length:
            nums.pop(i)
        
        return list(set(nums))

result 를 따로 만들지 않고 nums 로 끝낸건데... 매우 느림^^

length 보다 작은 건 무조건 pop pop 크레용pop

---

796. Rotate String

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

My Answer 1: Accepted (Runtime: 24 ms - 94.14% / Memory Usage: 14.1 MB - 73.92%)

class Solution:
    def rotateString(self, A: str, B: str) -> bool:
    	if A == B:
            return True
            
        head = ''
        i = 0
        while len(A) > 0 and i < len(B):
            if A[0] == B[i]:
                if B[i:] + head == A:
                    return True
                
            head += B[i]
            i += 1
        
        return False

A = "" & B = "" 처럼 A == B 의 경우는 미리 예외처리

B 에서 A[0] 를 찾기

A[0] 를 만나기까지의 문자들은 모두 head 에 넣어주고, 만났을 때 B[i:] + head == A 인지 비교