😊 LeetCode Easy Collections I - 20 Problems

0001. Two Sum / 0268. Missing Number

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dct = dict()
        for i in range(len(nums)):
            dct[nums[i]] = i
        for i in range(len(nums)):
            if (target-nums[i]) in dct:
                if i!=dct[target-nums[i]]:
                    return [i,dct[target-nums[i]]]

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

 

🧡 0001) [2, 7, 11, 15]를 list로 돌릴 때 target이 9일 경우 2 나 자신을 제외한 7이 list에 존재하는 지를 hash map O(1)로 구현해 상대적으로 빠른 시간 내에 정답 코드 구현 가능

🧡 0268) 먼저 sort()로 오름차순 정렬한 뒤, 맨 앞이 0이 아니면 바로 0 출력. index 1 이상일 경우 바로 앞의 index와의 차이가 1이 아니면 바로 앞의 index + 1을 출력. 맨 마지막까지 모두 정상적으로 +1이 다 되었다면 맨 마지막 숫자 출력

---

0020. Valid Parentheses / 0232. Implement Queue Using Stacks

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        for x in s:
            if stack:
                if stack[-1] == '(' and x == ')':
                    stack.pop()
                elif stack[-1] == '[' and x == ']':
                    stack.pop()
                elif stack[-1] == '{' and x == '}':
                    stack.pop()
                else:
                    stack.append(x)
            else:
                stack.append(x)
        if stack:
            return False
        else:
            return True

from collections import deque

class MyQueue:

    def __init__(self):
        self.stack_A, self.stack_B = [], []
        
    def push(self, x: int) -> None:
        self.stack_B.append(x)

    def pop(self) -> int:
        if self.stack_A:
            return self.stack_A.pop()
        else: #stack_B
            while self.stack_B:
                self.stack_A.append(self.stack_B.pop())
            return self.stack_A.pop()

    def peek(self) -> int:
        if self.stack_A:
            return self.stack_A[-1]
        else: #stack_B
            while self.stack_B:
                self.stack_A.append(self.stack_B.pop())
            return self.stack_A[-1]

    def empty(self) -> bool:
        if not self.stack_A and not self.stack_B:
            return True
        else:
            return False


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

 

🧡 0020) stack을 활용해 valid한 지 알아보는 문제. stack의 pop()과 [-1] indexing으로 O(1) 빠른 연산을 활용해 괄호의 쌍이 적절히 매칭되었는지 쉽게 구할 수 있다.

🧡 0232) Queue는 두 개의 stack을 활용해 만들 수 있다. 아래 그림을 참조.

: stack 두 개를 queue로 위 그림과 같이 만들 수 있다. 다만, stack_A 앞 부분 stack을 reverse한 결과와 stack_B를 그대로 붙인 결과가 queue. queue에 append()한 건 stack_B에 append() 연산과 동일. queue 맨 왼쪽 peek과 pop은 stack_A를 stack_A[-1] indexing과 pop() 연산과 동일.

---

0217. Contains Duplicate / 0013. Roman to Integer

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(set(nums)) != len(nums):
            return True
        else:
            return False

class Solution:
    def romanToInt(self, s: str) -> int:
        dct=dict()
        dct['I']=1
        dct['V']=5
        dct['X']=10
        dct['L']=50
        dct['C']=100
        dct['D']=500
        dct['M']=1000
        ans=0
        for x in range(len(s)):
            if x>=1:
                if s[x-1] == 'C' and s[x] in ['M','D']:
                    ans+=(dct[s[x]]-200)
                    continue
                elif s[x-1] == 'I' and s[x] in ['V','X']:
                    ans+=(dct[s[x]]-2)
                    continue
                elif s[x-1] == 'X' and s[x] in ['C','L']:
                    ans+=(dct[s[x]]-20)
                    continue
            ans+=dct[s[x]]
        return ans

 

🧡 0217) duplicate 허용 여부는 set 자료구조 활용

🧡 0013) I, C, X 예외 케이스만 각각 앞에 있는 문자에 따라 dict[]의 값을 일정 수 만큼 빼주고, 나머지의 경우는 일정 수를 dictionary의 value로 더해주면 된다.

---

0009. Palindrome Number / 0409. Longest Palindrome

class Solution:
    def isPalindrome(self, x: int) -> bool:
        x=''.join(str(x))
        if x==x[::-1]:
            return True
        else:
            return False

from collections import Counter
class Solution:
    def longestPalindrome(self, s: str) -> int:
        ans=0
        odd_exists = False
        freq = Counter(s)
        for x in freq:
            if freq[x]%2==0:
                ans+=freq[x]
            else:
                odd_exists = True
                ans+=(freq[x]-1)
        if odd_exists:
            ans+=1
        return ans

 

🧡 0009) 주어진 문자열 Palindrome으로 좌우 뒤집으면 끝

🧡 0409) Counter 함수를 활용하여 주어진 문자열의 frequency dictionary 생성. 최대한 긴 길이의 palindrome을 만들려면 주어진 frequency dictionary에서 짝수 개수의 frequency는 바로 add up. 홀수 개수의 frequency는 -1 하고 add up. 만약 홀수 개수의 문자가 존재한다면, 중앙에 1개 문자를 놓을 수 있으므로 +1.

---

0383. Ransom Note / 0242. Valid Anagram

from collections import Counter
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomNote_Counter = Counter(ransomNote)
        magazine_Counter = Counter(magazine)
        magazine_Counter_keys = magazine_Counter.keys()
        for letter in ransomNote_Counter:
            if letter not in magazine_Counter_keys:
                return False
            else:
                if ransomNote_Counter[letter] > magazine_Counter[letter]:
                    return False
        return True

from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_freq = Counter(s)
        t_freq = Counter(t)
        s_freq_keys = s_freq.keys()
        t_freq_keys = t_freq.keys()
        if s_freq_keys != t_freq_keys:
            return False
        for s_freq_key in s_freq_keys:
            if s_freq[s_freq_key] != t_freq[s_freq_key]:
                return False
        return True

 

🧡 0383) ransomNote의 freq dictionary와  magazine의 freq dictionary를 모두 구한다. 이후 ransoeNote_Counter의 key가 magazine_Counter에 존재하지 않거나, 존재하더라도 ransomNote_Counter의 key에 해당하는 value가 magazine_Counter의 key에 해당하는 value보다 크다면 magazine으로 더 이상 만들 수 없으므로 False. 그 외의 경우는 magazine으로 만들 수 있으므로 True

🧡 0242) anagram의 여부는 두 문자열의 Counter 결과로 만들어진 frequency dictionary 일치 여부로 알 수 있다. keys가 서로 일치하지 않으면 당연히 False. 서로 일치하더라도 빈도수가 다르면 만들 수 없으므로(ex ab와 aabb) 빈도수가 하나라도 다르다면 바로 False 리턴. 모든 for문을 다 거쳤다는 건 True이므로 True 리턴

---

0136. Single Number / 0069. Sqrt(x)

from collections import Counter
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        freq = Counter(nums)
        for x in freq:
            if freq[x] == 1:
                return x

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        elif x == 1: return 1
        start,end=1,x
        while start<=end:
            mid=(start+end)//2
            if x<mid*mid:
                end=mid-1
            elif x==(mid*mid):
                return mid
            else:
                ans=mid
                start=mid+1
        return ans

 

🧡 0136) 빈도수 1인 경우 Counter로 돌리면 됨.

🧡 0069) x의 sqrt(x)를 구하는 문제. 직접 O(n)으로 brute-force로 돌려도 되나, O(logn)으로 binary search 풀이도 가능. start와 end를 각각 1과 x로 잡고 중간 mid를 제곱한 결과가 x보다 큰 지, 같은 지, 작은 지에 따라 처리하는 문제. 

---

0374. Guess Number Higher or Lower / 0035. Search Insert Position

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        start,end=1,n
        while start<=end:
            mid=(start+end)//2
            if guess(mid) == 0:
                return mid
            elif guess(mid) == 1:
                start=mid+1
            else:
                end=mid-1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start,end=0,len(nums)-1
        ans=len(nums)
        while start<=end:
            mid=(start+end)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                ans=mid
                end=mid-1
            else:
                start=mid+1
        return ans

 

🧡 0374) predefined 되어 있는 guess() 함수를 활용해 1부터 n까지의 수 중 임의로 고른 수보다 up, same, down인지에 따라 탐색 범위 절반으로 줄여가며 확인. 탐색 범위 절반으로 줄여가며(이분탐색) target 탐색하므로 시간복잡도는 O(logn)

🧡 0035) 주어진 오름차순 배열에서 target이 어디 위치에 들어갈 지 index를 출력하는 문제. start와 end를 index 0과 index len(nums)-1로 설정하고 그 절반 index에 해당하는 원소보다 target이 큰지/작은지/같은지에 따라 binary search 진행. 이 때, target이 전체 list의 최댓값(맨 오른쪽 값)보다 크다면 default로 길이가 출력되게끔, ans = len(nums)로 설정.

---

0278. First Bad Version / 0121. Best Time to Buy and Sell Stock

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        if n == 1: return 1
        start,end=1,n
        while start<=end:
            mid=(start+end)//2
            if isBadVersion(mid):
                ans=mid
                end=mid-1
            else:
                start=mid+1
        return ans

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        cur_min = prices[0]
        for price in prices[1:]:
            ans = max(ans,price-cur_min)
            if price<cur_min:
                cur_min=price
                
                
        return ans

 

🧡 0278) start와 end를 각각 1과 n으로 두고, mid의 isBadVersion() 결과에 따라 update. 가장 첫번째 BadVersion의 번호를 구하므로 isBadVersion이 맞을 때 ans = mid 설정

🧡 0121) DP 문제로, prices list를 for문으로 돌리면서 앞의 list의 최솟값 update. 현재 원소의 위치 index가 i라면 index 0 ~ (i-1)까지 해당하는 원소 중에 최솟값이 prices[i]보다 작다면 ans update(이 때 ans는 최댓값 유지). 앞부터 끝까지 누적해서 결과를 update하는 알고리즘이므로 bottom-up DP

---

0070. Climbing Stairs / 0733. Flood Fill

class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0]*(n+1)
        if n == 1:
            return 1
        else:
            dp[1],dp[2]=1,2
            for x in range(3,n+1):
                dp[x] = dp[x-2]+dp[x-1]
            return dp[n]

from collections import deque

def BFS(graph, visited, start,color):
    m,n=len(graph),len(graph[0])
    start_color = graph[start[0]][start[1]]
    graph[start[0]][start[1]] = color
    queue = deque([start])
    visited[start[0]][start[1]] = True
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    while queue:
        v=queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if not visited[nx][ny] and graph[nx][ny] == start_color:
                    visited[nx][ny] = True
                    graph[nx][ny] = color
                    queue.append((nx,ny))

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        visited=[[False]*len(image[0]) for _ in range(len(image))]
        BFS(image,visited,(sr,sc),color)
        return image

 

🧡 0070) bottom-up DP 유형으로, n개의 step을 건너는데 1개 또는 2개의 step을 사용해 건너는 가짓수를 구하는 유형. dp[n]을 n개의 계단으로 건너는 가짓수라면, 점화식은 dp[n] = dp[n-1] + dp[n-2]로 쉽게 내릴수 있다(n≥3) 

🧡 0733) flood-fill 유형으로, 시작점부터 동일한 부분만 주어진 color로 칠해주면 된다. dx,dy로 방향벡터만들어서 simulation 돌리면서 BFS 형식으로 '조건에 맞는' 인접노드만 동일 color로 채워나가면 된다.

---

0463. Island Perimeter / 0844. Backspace String Compare

from collections import deque

def BFS(graph, visited, start):
    perimeter = 0
    queue = deque([start])
    visited[start[0]][start[1]] = True
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    while queue:
        vx,vy = queue.popleft()
        near_islands=4
        for i in range(4):
            nx,ny=vx+dx[i],vy+dy[i]
            if 0<=nx<len(graph) and 0<=ny<len(graph[0]):
                if graph[nx][ny] == 1:
                    near_islands-=1
                    if not visited[nx][ny]:
                        visited[nx][ny] = True
                        queue.append((nx,ny))
        perimeter+=near_islands
    return perimeter


class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        row,col=len(grid),len(grid[0])
        visited=[[False]*col for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    return BFS(grid,visited,(i,j))

def get_stack(string):
        stack = []
        for s in string:
            if s == '#':
                if stack: stack.pop()
            else:
                stack.append(s)
        return stack

class Solution:

    def backspaceCompare(self, s: str, t: str) -> bool:
        after_s = get_stack(s)
        after_t = get_stack(t)
        if after_s == after_t:
            return True
        else:
            return False

 

🧡 0463) 연결영역의 둘레를 구하는 문제. 가능 near_islands = 4라 설정한 뒤, 주위 갈 수 있는 곳 있을 때마다 -1. 4방향 각각 확인 뒤 update된 near_islands 값을 perimeter에 계속 add up.

🧡 844) 스택 문제. #이 있다면 stack에 무엇이 있을 경우 바로 pop(). backspace로 모두 지우고 난 후 같은지 다른 지 서로 비교하면 끝

---