[leetcode] 162, 166, 350, 387

350. Intersection of Two Arrays II

https://leetcode.com/problems/intersection-of-two-arrays-ii/

My Answer 1: Accepted (Runtime: 64 ms - 21.55% / Memory Usage: 14.5 MB - 43.82%)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums2) < len(nums1):
            nums1, nums2 = nums2, nums1
        
        ans = []
        for i in range(len(nums1)):
            if nums1[i] in nums2:
                ans.append(nums1[i])
                nums2.remove(nums1[i])
        
        return ans

길이가 더 작은 nums 를 nums1 로 잡아줌

nums1 값이 nums2 에 있으면 nums2 에서 제거 & ans 에 추가

아니면 Counter 로 nums2 의 개수를 구해놓고
nums1 의 개수가 포함되는지 확인해도 될 듯

---

387. First Unique Character in a String

https://leetcode.com/problems/first-unique-character-in-a-string/

My Answer 1: Accepted (Runtime: 132 ms - 51.78% / Memory Usage: 14.1 MB - 99.63%)

class Solution:
    def firstUniqChar(self, s: str) -> int:
        ans = 0
        dic = {}
        
        for i in range(len(s)):
            if s[i] in dic:
                dic[s[i]][0] += 1
            else:
                dic[s[i]] = [1, i]
        
        for k, v in dic.items():
            if v[0] == 1:
                return v[1]
        return -1

dic 에 각 문자마다 [개수, 인덱스] 로 묶어서 저장

다시 dic 를 보면서 개수 (v[0]) 가 1 인 값만 return

아니면 그냥 Counter 로 value 가 1 인 key return 해도 될 듯

---

162. Find Peak Element

https://leetcode.com/problems/find-peak-element/

My Answer 1: Accepted (Runtime: 40 ms - 92.97% / Memory Usage: 14.2 MB - 98.24%)

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i-1] > nums[i]:
                return i-1
        
        return len(nums)-1

nums[i-1] 과 nums[i] 를 비교해서 decreasing 하면 바로 i-1 return

decreasing 하는 부분이 없다면 마지막 값이 peak 니까 len(nums)-1 return

You must write an algorithm that runs in O(log n) time.

라서 Binary Search 로 해보려 했지만

• 아무 peak 나 return 하면 된다
• 계속 increasing 일 경우는 마지막 인덱스가 peak 이 된다
• 계속 decreasing 일 경우는 첫번째 인덱스가 peak 이 된다

이 세가지를 늦게 알아서... 실패

Solution 1: Accepted (Runtime: 44 ms - 79.04% / Memory Usage: 14.4 MB - 44.32%)

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        
        while l < r:
            m = (l + r) // 2
            
            if nums[m] < nums[m + 1]:
                l = m + 1
            else:
                r = m

        return r

nums[l], nums[m], nums[r] 값끼리 비교하는게 아니라

nums[m] 과 nums[m + 1] 를 비교

if nums[m] < nums[m + 1]: => increasing 이니까 l 을 움직여줘서 더 오른쪽으로 가기
if nums[m] >= nums[m + 1]: => peak 의 가능성이 있으니까 r 을 m 으로 당겨줌

외우자!!!

---

166. Fraction to Recurring Decimal

https://leetcode.com/problems/fraction-to-recurring-decimal/

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

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator % denominator == 0:
            return str(numerator // denominator)
        
        neg = 0
        if numerator < 0:
            neg ^= 1
        if denominator <0:
            neg ^= 1
        
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        num = numerator//denominator
        numerator = numerator % denominator
        ans = ""
        if neg:
            ans = "-"
        ans += str(num) + "."
        frac = ""
        
        nums = []
        while numerator:
            if numerator in nums:
                idx = nums.index(numerator)
                ans += frac[:idx]
                frac = frac[idx:]
                break
            nums.append(numerator)
            numerator *= 10
            frac += str(numerator // denominator)
            numerator %= denominator
        
        if numerator == 0:
            ans += frac
        else:
            ans += "(" + frac + ")"
        
        return ans

이 문제 보자마자 귀찮았다...^^

1. 나눠 떨어지는 건 바로 string 으로 바꿔서 return

2. 나머지는 음수인지 판단
   => neg 는 음수의 개수에 따라 1 개면 1 / 0 또는 2 개면 0 이 저장됨

3. num 에 정수부분 몫을 구해두고
   이제 소수부분을 구해줘야 하니까 numerator 를 numerator % denominator 로 변경

4. ans 에 정수부분 값과 소숫점 추가 (음수면 - 붙여주기)

5. while 문 돌면서 numerator 는 nums 에 저장
   numerator 에 10 을 계속 곱해주면서 몫 구하기 => frac 에 저장

6. 이미 만난 numerator 라면 순환한다는 거니까 break
   frac 은 소수부분 전체를 갖고 있기 때문에 순환 소수 부분만 따로 처리를 해줘야함
   => nums.index(numerator) 로 순환 시작 인덱스를 구해서
   frac 의 순환하지 않는 소수부분은 ans 에 저장하고
   frac 은 순환하는 소수부분만 저장해둠

7. numerator 가 0 이라면 순환하지 X
   => 바로 frac 붙여주고 return

8. 순환한다면 괄호 추가해서 return