[leetcode] 56, 62, 125, 136

136. Single Number

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

My Answer 1: Accepted (Runtime: 120 ms - 97.78% / Memory Usage: 16.6 MB - 59.92%)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = collections.Counter(nums)
        
        for k, v in count.items():
            if v == 1:
                return k

Counter 로 1 번 나오는 값 찾아주기

You must implement a solution with a linear runtime complexity and use only constant extra space.

라길래..

(len(nums)+1) // 2 가 숫자 종류의 갯수가 되는 점과
하나빼고 나머지는 다 두번씩 나온다는 점을 이용해서
리스트 절반을 나눠서 어떻게 해보려고 했으나
도저히 O(n) 런타임과 O(1) space 를 만족하지 못하겠음..

그래서 보니까 Bit 연산만이 가능..^^

Solution 1: Accepted (Runtime: 128 ms, faster than 84.10% / Memory Usage: 16.5 MB, less than 96.45%)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        
        for i in nums:
            a ^= i
            
        return a

XOR 을 이용하면 A ^ A = 0 A ^ B ^ A = B 처럼 혼자인 값만 return 됨

알아두자!!

---

125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/

My Answer 1: Accepted (Runtime: 56 ms - 26.81% / Memory Usage: 14.5 MB - 93.71%)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        
        s2 = ""
        for i in range(len(s)):
            if (ord(s[i]) > 96 and ord(s[i]) < 123) or (ord(s[i]) > 47 and ord(s[i]) < 58):
                s2 += s[i]
        
        for i in range(len(s2)//2):
            if s2[i] != s2[len(s2)-i-1]:
                return False
        
        return True

다른 라이브러리를 쓰고 싶지 않아서... 아스키코드 이용해서 풂
(re 라이브러리를 쓰면 re.sub('[^0-9a-zA-Z]', '', s) 한번에 공백, 특수문자 제거 가능)

소문자로 모두 바꿔준 후 숫자 & 문자 아스키 범위에 드는 문자들만 s2 에 저장
s2 는 절반으로 나눠서 대칭되는지 확인

Solution 1: Accepted (Runtime: 56 ms - 32.06% / Memory Usage: 14.6 MB - 62.39%)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        clear = ""
        for i in range(len(s)):
            if s[i].isalpha() or s[i].isdigit():
                clear += s[i].lower()
        
        for i in range(0, len(clear)//2):
            if clear[i] != clear[len(clear)-i-1]:
                return False
        
        return True

저번에 내가 푼 방식인데 아스키 쓰는 것과 같은 역할을 수행함

근데 isalpha(), isdigit() 함수써서 문자, 숫자만 clear 에 저장하는게 나은듯

---

56. Merge Intervals

https://leetcode.com/problems/merge-intervals/

My Answer 1: Accepted (Runtime: 92 ms - 30.09% / Memory Usage: 16.2 MB - 11.24%)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        
        intervals.sort()
        
        for i in range(len(intervals)):
            for j in range(len(ans)):
                if ans[j][0] <= intervals[i][0] <= ans[j][1]:
                    ans[j][1] = max(ans[j][1], intervals[i][1])
                    intervals[i][0] = -1
                    break
            if intervals[i][0] != -1:
                ans.append(intervals[i])
        
        return ans

시작 값을 기준으로 정렬 먼저 해주기

인터벌마다 어떤 구간에 속하는지 확인

인터벌의 시작값으로 ans 의 구간들 중 속하는 곳이 있는지 판단해서
있으면 그 구간을 더 넓게 update & 속했다는 표시로 intervals[i][0] = -1 해주기

어디에도 속하지 않은 인터벌은 그 자체로 ans 에 append

My Answer 2: Accepted (Runtime: 84 ms - 76.42% / Memory Usage: 16.1 MB - 55.02%)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        
        ans = [intervals[0]]
        
        for i in range(1, len(intervals)):
            if ans[-1][1] < intervals[i][0]:
                ans.append(intervals[i])
            else:
                ans[-1][1] = max(ans[-1][1], intervals[i][1])
        
        return ans

생각해보니까 정렬을 했으니까
ans 의 마지막 값에 인터벌의 시작 값이 포함되는지 확인하면 됨

그럼 for 문 하나로 더 빠르게 할 수 있다!!

---

62. Unique Paths

https://leetcode.com/problems/unique-paths/

My Answer 1: Accepted (Runtime: 36 ms - 21.69% / Memory Usage: 14.3 MB - 39.83%)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = collections.defaultdict(int)
        dp[(0,0)] = 1
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                dp[(i,j)] = dp[(i-1,j)] + dp[(i, j-1)]
        
        return dp[(m-1,n-1)]

행렬, 경우의 수... 를 보니 dp 를 써야겠다고 생각

그림을 그려보니까
dp[(i,j)] 값은 dp[(i-1,j)] + dp[(i, j-1)] 가 된다는 규칙을 발견

dp 를 defaultdict 로 만들어서 존재하지 않으면 디폴트 값으로 0 을 가져오도록 함

dp 의 key 값을 튜플로 주는 방법 말고 애초에 m*n 크기의 dp 를 생성해서 해도 됨