pjaehyun의 개발일지

문제

https://leetcode.com/problems/permutations/description/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

중복되지 않은 정수가 주어질 때 만들 수 있는 모든 순열을 만들어서 정답을 반환하라. 순서는 상관없음

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        nums_length = len(nums)
        result = []
        visited = [False] * nums_length
        
        def dfs(arr):
            if len(arr) == nums_length:
                result.append(arr[:])

            for i in range(nums_length):
                if not visited[i]:
                    visited[i] = True
                    arr.append(nums[i])
                    dfs(arr)
                    arr.pop()
                    visited[i] = False
        dfs([])
        return result

백트래킹을 이용하여 문제 풀이

1. 방문체크를 하기위해 visited를 초기화해준다

2. 재귀함수를 통해 모든 경우를 탐색한다

    - 현재 위치가 방문한곳이 아닐때에만 dfs함수 호출

    - arr에 현재 값 삽입 

    - dfs에 값이 추가된 arr로 다시 호출한다

    - 호출한 dfs가 종료되면 arr에 들어간 값을 pop하고 visited[i]를 다시 방문할 수 있도록 False로 변경

    - arr의 길이가 nums_length와 같으면 result에 추가해준다

3. 모든 재귀함수가 종료되면 result를 반환한다

문제

https://leetcode.com/problems/where-will-the-ball-fall/

You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.

• A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
• A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.

We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

크기가 m * n인 grid 배열이 주어지고, n개의 공이 주어질 때 공의 마지막 위치를 구해서 반환해라.

• 공이 오른쪽 하단으로 내려갈 때는 grid가 1로 표시된다
• 공이 왼쪽 하단으로 내려갈 때는 grid가 -1로 표시된다

answer[i]는 공이 굴러가는 경로가 V 모양을 하고있거나, 배열 밖으로 나갈때에는 -1, 가장 끝까지 내려왔을 때는 현재 column의 위치를 입력한다

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        N, M = len(grid), len(grid[0])
        result = [0] * M
        def dfs(x, y):
            if x >= N:
                return y
            if grid[x][y] == 1:
                if y + 1 >= M:
                    return -1
                if grid[x][y + 1] == -1:
                    return -1
                return dfs(x + 1, y + 1)
            if grid[x][y] == -1:
                if y - 1 < 0:
                    return -1
                if grid[x][y - 1] == 1:
                    return -1
                return dfs(x + 1, y - 1)
        for i in range(M):
            result[i] = dfs(0, i)
        return result

깊이 우선 탐색을 이용하여 문제 풀이

1. grid[x][y]가 1이면 오른쪽으로 이동하고 -1이면 왼쪽으로 이동

2. 현재 위치가 1(오른쪽으로이동)이고 grid[x][y+1]이 -1일 때 길이 막히기 때문에 -1을 반환

3. 마찬가지로 현재 위치가 -1(왼쪽으로이동)일 때 grid[x][y-1]이 1일 때 길이 막히기 때문에 -1을 반환

4. x의 크기가 N보다 크거나 같으면 현재 y를 반환한다.

5. 모든 공을 출발시켜서 해당 값을 받아서 결과를 반환한다.

문제

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

문제풀이 코드

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n, b = len(grid), len(grid[0]), k
		
        # 최단거리로 가는 거리보다 k가 크다면 언제나 최단거리로 이동할 수 있음
        if k >= m + n - 3:
            return m + n - 2
            
        dx, dy = [0, -1, 0, 1], [1, 0, -1, 0]
        visited = set()
        def bfs():
            dq = deque()
            dq.append((0,0,b,0))
            
            while dq:
                x, y, crush, distance = dq.popleft()
                if x == m - 1 and y == n - 1:
                    return distance
                
                for i in range(4):
                    xx, yy = x + dx[i], y + dy[i]
                    if 0 <= xx < m and 0 <= yy < n and crush >= grid[xx][yy]:
                        if (xx, yy, crush-grid[xx][yy]) not in visited:
                            dq.append((xx, yy, crush-grid[xx][yy], distance+1))
                            visited.add((xx, yy, crush-grid[xx][yy]))
            return -1
        return bfs()

최단거리를 구하는 문제로 bfs로 문제 풀이

visited: 중복 방문을 방지하기위해 set으로 초기화

crush: 벽을 부술 수 있는 남은 횟수

distance: 출발지부터 현재 위치까지의 거리

1. deque에 x, y, 벽을 부술수있는 횟수, 거리를 초기값으로 세팅

2. 일반적인 bfs 로직에서 벽을 부술 수 있는 횟수가 현재위치의 값보다 크고

3. 방문한적이 없을 때 dq에 삽입해준다.

4. bfs가 종료되고 받는 return값을 반환해준다.

문제

https://leetcode.com/problems/earliest-possible-day-of-full-bloom/

You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each:

• plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total.
• growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.

From the beginning of day 0, you can plant the seeds in any order.

Return the earliest possible day where all seeds are blooming.

Example 1:

문제풀이 코드

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        min_grow = 0
        result = 0
        for plant, grow in reversed(sorted(zip(plantTime, growTime), key=lambda x:x[1])):
            result = max(result, min_grow + plant + grow)
            min_grow += plant
        return result

탐욕 알고리즘

1. 모든 꽃을 심기위해서는 최소 plantTime의 합이 필요하기 때문에, growTime이 이 문제의 key가 된다

2. growTime 큰 순서대로 씨앗이 심어지면 가장 최소시간으로 모든 꽃을 피울 수 있게된다.

3. min_grow는 현재 심어진 씨앗의 최소 길이로 min_grow 이후부터 씨앗을 심을 수 있다

4. plantTime과 growTime을 하나의 배열로 합친다음 growTime이 큰 순서대로 정렬한다

5. min_grow + 씨앗 심는 시간 + 꽃이 피는 시간을 계산하여 result를 계속 변경해준다.

6. 씨앗을 심었으면 min_grow는 현재 씨앗을 심은 시간을 더해준다

7. 반복문이 종료되면 result에는 꽃을 피우는 최단시간이 들어있기 때문에 그대로 반환한다

문제

https://leetcode.com/problems/group-anagrams/

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Example 2:

Example 3:

문제풀이 코드

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        
        for s in strs:
            key = ''.join(sorted(s))
            anagrams[key].append(s)
        return list(anagrams.values())

1. 결과를 저장할 딕셔너리를 defaultdict로 선언해준다(일반 dict로 선언하면 key가 없을 때 세팅해주는 경우가 생기기때문)

2. 반복문을 돌면서 strs에 들어있는 단어를 알파벳순으로 정렬하여 해당 정렬된 단어를 key값, 현재 단어를 value에 추가해준다

3. 반복문이 종료되면 같은 key값을 가진 단어들이 같은 value에 들어있기 때문에 anagrams의 values를 리스트로 변환하여 반환한다.

문제

https://leetcode.com/problems/continuous-subarray-sum/description/

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Example 2:

Example 3:

문제풀이 코드

첫번째 풀이

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        for i in range(1, len(nums)):
            for j in range(i-1, -1, -1):
                nums[j] = nums[i] + nums[j]
                if nums[j] % k == 0:
                    return True
        return False

첫번째로 풀때는 무식하게 이중 for문을 돌려서 풀었는데, 당연하게도 시간초과로 해결되지 않았다...

두번째 풀이

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        _sum, dic = 0, {0:-1}
        for idx, num in enumerate(nums):
            # k현재까지 합계의 나머지
            _sum = (_sum + num) % k
            # 같은 나머지가 나온다면 이전에 나왔던 위치에서 현재까지 k의 배수가 더해진 것
            # 같은 나머지가 존재하는 위치가 현재 위치와 거리가 2이상이 되어야함:
            if _sum not in dic:
                dic[_sum] = idx
            elif idx - dic[_sum] >= 2:
                return True
        return False

딕셔너리(Hash Table)를 이용한 풀이

1. 나머지의 인덱스와 합계를 선언

2. 현재 위치까지의 합계의 나머지를 구한다.

3. 현재 위치까지의 합계의 나머지가 딕셔너리에 들어가있다면 현재 위치의 값에서 딕셔너리의 값을 뺀 값이 2이상일 때 True를 반환하고

4. 나머지가 딕셔너리에 들어가있지 않으면 값을 넣어준다

5. 반복문이 종료되면 False를 반환한다

문제

https://leetcode.com/problems/top-k-frequent-words/description/

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Example 2:

문제풀이 코드

첫번째 풀이

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        word_count = {}
        result = []
        for w in words:
            try:
                word_count[w] += 1
            except:
                word_count[w] = 1
        sorted_word = sorted([[k, v] for k, v in word_count.items()])
        sorted_word.sort(key=lambda x:x[1], reverse=True)
        for i in range(k):
            result.append(sorted_word[i][0])
        return result

1. 직접 단어의 수를 카운트해서 dictionary에 저장

2. 저장된 값을 (k,v) 튜플형태로 만들어서 k값 기준으로 정렬된 리스트 형태로 변경한다

3. 해당 리스트를 v값기준으로 다시한번 정렬한다(단어가 많은 순으로 정렬하되 같으면 알파벳 사전순으로 정렬된다)

4. 만들어진 리스트에서 k개 만큼 원소를 담아서 반환한다. 

두번째 풀이

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        word_count = dict(Counter(words))
        word_count = sorted(word_count.items())
        word_count.sort(key=lambda x:x[1], reverse=True)
        return [a for (a, b) in word_count[:k]]

첫번째 풀이와 같은 방식으로 풀었지만 Counter를 사용하여 단어의 갯수를 구하고, return을 list comprehension으로 바로 반환함으로 코드를 간결하게 변경했다.

세번째 풀이

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        word_count = dict(Counter(words))
        result = []
        max_heap = []
        heapq.heapify(max_heap)
        
        for k1, v in word_count.items():
            heapq.heappush(max_heap, (-v,k1))
            
        for i in range(k):
            item = heapq.heappop(max_heap)
            result.append(item[1])
        return result

max heap을 이용하여 문제 풀이 

1.  Counter를 이용하여 단어의 갯수를 센다

2. 단어와 해당 단어의 갯수를 heap에 삽입한다

3. k번만큼 반복을 하며 heap에서 pop을하고 결과에 집어넣어준다.

4. 반복문이 종료되면 결과를 반환한다.

문제

https://leetcode.com/problems/minimum-window-substring/

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

길이가 각각 m과 n인 두 개의 문자열 s와 t가 주어지면 t의 모든 문자(중복 포함)가 포함되는 s의 최소 부분 문자열을 반환합니다.

Example 1:

Example 2:

Example 3:

문제풀이 코드

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t = Counter(t)
        _max, count = inf, len(t)
        start, end = 0, 0
        result = ""
        
        while end < len(s):
            # find end point
            while end < len(s) and count != 0:
                if s[end] in t:
                    t[s[end]] -= 1
                    if t[s[end]] == 0:
                        count -= 1
                end += 1

            # find start point
            while start <= end and count == 0:
                if _max > end - start:
                    _max = end-start
                    result = s[start:end]
                if s[start] in t:
                    t[s[start]] += 1
                    if t[s[start]] > 0:
                        count += 1
                start += 1
        return result

슬라이딩 윈도우 기법으로 문제풀이

1. 찾아야하는 문자들을 Counter를 통해 갯수를 세어준다.

2. 모든 문자의 갯수가 0보다 같거나 작을 때 end포인트 세팅 종료

3. start 포인트 반복문이 돌 때 _max > end - start 면 result를 더 짧은 문자열로 바꿔준다.

4. start 포인트 세팅을 통해 현재 문자가 문자열 t안에 있으면 해당 문자의 갯수를 +1 해준다.

5. end가 문자열s의 길이보다 크거나 같을 때 반복문 종료 후 결과를 반환한다