[leetcode] 128, 130, 204, 206

204. Count Primes

https://leetcode.com/problems/count-primes/

My Answer 1: Time Limit Exceeded (17 / 21 test cases passed.)

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        
        primes = set()
        for i in range(2, n):
            isPrime = 1
            for p in primes:
                if i % p == 0:
                    isPrime = 0
                    break
            if isPrime:
                primes.add(i)
        
        return len(primes)

소수들을 primes 에 넣어주면서
각 숫자마다 약수가 primes 에 존재하는지 확인해서
없으면 소수니까 primes 에 넣어주고
마지막에 길이 return

Solution 1: Accepted (Runtime: 676 ms - 48.47% / Memory Usage: 25.7 MB - 49.76%)

import math
class Solution:
    def countPrimes(self, n: int) -> int:
        if n == 0 or n == 1:
            return 0
        prime = [True]*(n)
        count = 0
        for i in range(2, int(math.sqrt(n))+1):
            if prime[i]:
                j = i*i
                while j < n:
                    prime[j] = False
                    j += i
        for p in range(2, len(prime)):
            if prime[p]:
                count += 1
        return count

2 ~ sqrt(n) 의 범위로 for 문 돌려서

i 의 제곱에 i 씩 더해가면서 n 보다 작으면 prime = false 해줌
=> 배수들은 다 false 해주는 것
=> i = 2 -> 4(2^2), 6, 8, ... 는 false

이대로 외우는 걸로..^^

---

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

My Answer 1: Accepted (Runtime: 36 ms - 65.32% / Memory Usage: 15.4 MB - 93.18%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        
        nexth = head.next
        prev = None
        
        while head:
            nexth = head.next
            head.next = prev
            prev = head
            head = nexth
        
        return prev

prev 와 next 를 잡아서
head.next 에 prev 를 연결하고 head 는 다음 next 로 이동시킴

prev 는 현재 head 로, head 는 다음 next 로 이동

ex)

input: 1 -> 2 -> 3 -> 4 -> 5

prev = None			| head = 1	| next = 2 -> 3 -> 4 -> 5
prev = 1			| head = 2	| next = 3 -> 4 -> 5
prev = 2 -> 1			| head = 3	| next = 4 -> 5
prev = 3 -> 2 -> 1		| head = 4	| next = 5
prev = 4 -> 3 -> 2 -> 1		| head = 5	| next = None
prev = 5 -> 4 -> 3 -> 2 -> 1	| head = None	| next = None

result: 5 -> 4 -> 3 -> 2 -> 1

---

128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

My Answer 1: Accepted (Runtime: 212 ms - 50.68% / Memory Usage: 22.8 MB - 98.48%)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        
        nums.sort()
        ans = 1
        idx = 0
        for i in range(len(nums)-1):
            if nums[i] + 1 != nums[i+1]:
                ans = max(ans, i+1-idx)
                if nums[i] == nums[i+1]:
                    idx += 1
                else:
                    idx = i+1
            elif i == len(nums)-2:
                ans = max(ans, i+2-idx)
        
        return ans

정렬 후, 연속 되는 만큼의 최대 길이 update

idx 는 연속의 시작 인덱스, i 는 연속의 끝 인덱스가 됨
같은 값이 나오면 idx + 1 만 해줌

O(n) 은 아니다...^^

Solution 1: Accepted (Runtime: 176 ms - 95.90% / Memory Usage: 25.8 MB - 73.68%)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        best = 0
        for x in nums:
            if x - 1 not in nums:
                y = x + 1
                while y in nums:
                    y += 1
                best = max(best, y - x)
        return best

연속되는 숫자들의 시작 값 x 와 끝 값 y 를 찾는 방식

우선 nums 를 set 로 만들기

x - 1 값이 nums 에 없으면 연속의 시작이라는 의미!!
y = x+1 로 잡고 y 부터 1 씩 증가 시키면서 연속의 끝도 찾음

best 는 최대 길이 y - x 로 update

for 문 안에 while 과 in 을 써도 O(n) 인게 신기하다

---

130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions/

My Answer 1: Accepted (Runtime: 136 ms - 72.36% / Memory Usage: 16.5 MB - 21.65%)

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        
        dp = []
        for i in range(m):
            dp.append([0]*n)
        
        def func(i, j):
            if dp[i][j]:
                return
            
            dp[i][j] = 1
            board[i][j] = "X"
            
            if i > 0 and board[i-1][j] == "O":
                func(i-1, j)
            if j > 0 and board[i][j-1] == "O":
                func(i, j-1)
            if i < m-1 and board[i+1][j] == "O":
                func(i+1, j)
            if j < n-1 and board[i][j+1] == "O":
                func(i, j+1)
            
            board[i][j] = "O"
            
        
        for i in range(m):
            if board[i][0] == "O":
                func(i, 0)
            if board[i][n-1] == "O":
                func(i, n-1)
        
        for j in range(1, n-1):
            if board[0][j] == "O":
                func(0, j)
            if board[m-1][j] == "O":
                func(m-1, j)
        
        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    board[i][j] = "X"

테두리 중에 O 들만 재귀 함수 돌려서 이어지는 O 들은 모두 dp = 1 로 설정

마지막에 dp 값이 0 인 애들은 모두 X 로 바꿔줌