[Mock] Microsoft 4

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: 36 ms - 18.83% / Memory Usage: 14.3 MB - 48.93%)

class Solution:
    def rotateString(self, A: str, B: str) -> bool:
        # 첨부터 같으면 True
        if A == B:
            return True
        
        # 길이가 다르면 무조건 False
        if len(A) != len(B):
            return False
        
        # B: 원본, B2: A 랑 같은지 확인하는 용도 (slice)
        B2 = B
        for i in range(len(B)):
            if B[i] == A[0]:
                B2 = B[i:] + B[:i]
                if A == B2:
                    return True
        
        return False

B 를 A[0] 값을 기준으로 slice 해주면서 A 랑 B 랑 같은지 확인

My Answer 2: Accepted (Runtime: 28 ms - 83.65% / Memory Usage: 14.4 MB - 15.26%)

class Solution:
    def rotateString(self, A: str, B: str) -> bool:
        # 첨부터 같으면 True
        if A == B:
            return True
        
        # 길이가 다르면 무조건 False
        if len(A) != len(B):
            return False
        
        # 시작 값 (A[0]) 이 없으면 False => 요거 추가했더니 빨라짐
        if A[0] not in B:
            return False
        
        # 빨리 찾기 위해서 B 도 A[0] 값부터 시작하도록 해줌
        B = B[B.index(A[0]):] + B[:B.index(A[0])]
        # B: 원본, B2: A 랑 같은지 확인하는 용도 (slice)
        B2 = B
        for i in range(len(B)):
            if B[i] == A[0]:
                B2 = B[i:] + B[:i]
                if A == B2:
                    return True
        
        return False

예외를 더 추가해주니까 빨라졌다.

KMP

---

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: 108 ms - 94.32% / Memory Usage: 15.5 MB - 26.25%)

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # 분명 시작은 easy 였는데 어느새 Medium 이 되어버린~...
        numsCount = collections.Counter(nums)
        
        # n // 3 보다 큰 값들만 찾기
        mv = len(nums) // 3
        
        result = []
        for key, val in numsCount.items():
            if val > mv:
                result.append(key)
        
        return result

Counter 이용해서 numsCount 구해주고

len(nums) // 3 보다 큰 value 값들만 result 에 append

My Answer 2: Accepted (Runtime: 132 ms - 15.62% / Memory Usage: 15.2 MB - 97.97%)

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # 분명 시작은 easy 였는데 어느새 Medium 이 되어버린~...
        
        nums.sort()
        
        result = set()
        now = nums[0]
        cnt = 0
        for i in range(len(nums)):
            if now == nums[i]:
                cnt += 1
            if now != nums[i]:
                now = nums[i]
                cnt = 1
            if cnt > len(nums) // 3:
                result.add(now)
        
        return result

sort 하고 cnt 로 세면서 if cnt > len(nums) // 3: 경우에만 result 에 넣는 식으로도 했는데

훨~씬 느리다