배극곰의 IT식량창고

문제링크

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

문제설명

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:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

문제풀이

처음에 문제를 보고 떠오른 아이디어가

각 아이템의 문자열을 정렬을 해서 비교하는 문제이려나 하는 막연한 생각이 들었다.

하지만 그럼 소트 메소드를 쓰면 nlogn인데 for문 안에서 돌려야하니 시간복잡도가 n^2logn 이잖아?.. 하고 과감히 버렸던 아이디어 였지만,

고민끝에 답이 나오지않아 검색한 결과

1. 각 item의 문자열을 정렬하고 => 아나그램이라면 정렬한 문자열이 서로 같을테니까

2. 딕셔너리를 활용.

    { 아나그램: 문자열 } 형태로 삽입한다.

3. 딕셔너리 값들을 정답 리스트에 삽입

 하는 로직으로 구현하면 된다.

코드

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        myDict = {}
        answer = []

        for item in strs:
            anagram = "".join(sorted(item))
            if anagram not in myDict:
                myDict[anagram] = [item]
            else:
                myDict[anagram].append(item)

        for item in myDict:
            answer.append(myDict[item])

        return answer

        # 1. 각 알파벳들을 쪼개서 정렬
        # 2. {애너그램: 원래문자열} 형태로 딕셔너리 삽입
        # 3. 같이 묶여있는 값들 리스트에 삽입 => 리스트 형태로 출력해야하므로

문제링크

https://leetcode.com/problems/longest-increasing-subsequence/

문제설명

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

문제풀이

LIS(가장 긴 증가하는 부분 수열)을 구하는 문제로,

대표적인 풀이 방법으로 DP를 사용하는 것이 있다.

D[i]: i번째 원소까지 증가하는 수열의 길이를 저장하는 배열이라 두자.

그리고 i가 순회하는 동안 j가 i번째 까지 순회하며 해당값을 비교해 j인덱스에 위치한 원소가 더 작다면,

D[i]값을 갱신한다. 이때, 원래 존재하는 (D[i]값)과 (D[j]에 1을 더한값)을 비교하여 큰수를 저장.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        # 가장 긴 증가하는 수열의 길이를 출력
        # ex) [10, 9, 2, 5, 3, 7, 101, 18]
        # Can you come up with an algorithm that runs in O(nlogn)
        # D[i]는? i번째까지 증가하는 수열의 길이

        N = len(nums)
        D = [1] * N
        
        for i in range(1, N):
            for j in range(i):
                if nums[i] > nums[j]:
                    D[i] = max(D[i], D[j]+1)

        return max(D)

하지만 해당 방법으로 풀게 되면 최악의 상황에서 O(N^2)의 시간복잡도를 갖게된다.

따라서 O(NlogN)까지 줄일 수 있는 방법이 DP + binary search 를 활용한 방법이 있다.

코드

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        # 가장 긴 증가하는 수열의 길이를 출력
        # ex) [10, 9, 2, 5, 3, 7, 101, 18]
        # Can you come up with an algorithm that runs in O(nlogn)
        # D[i]는? i번째까지 증가하는 수열의 길이

        lis = [nums[0]]
        for num in nums:
            # 현재요소가 마지막 요소보다 큰 경우 추가 
            if num > lis[-1]:
                lis.append(num)
            else:
                l, r = 0, len(lis) - 1
                while l < r:
                    mid = (l + r) // 2
                    # 이진탐색을 통한 값
                    if lis[mid] < num:
                        l = mid + 1
                    else:
                        r = mid
                lis[l] = num
                
        return len(lis)

문제링크

https://leetcode.com/problems/pacific-atlantic-water-flow/description/

문제설명

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 105

문제풀이

처음엔 여타 그래프 탐색 문제를 풀듯이 인접행렬로 BFS 돌려서 조건에 맞게 좌표를 산출하면 되겠거니 하는 안일한 생각이었다.

하지만 이중for문으로 모든 좌표에서 BFS를 시행하는 것이 과연 맞는 전략일까 라는 의문이 들었고,

또 우측, 하측에 있는 Atlantic 바다와 좌, 상측에 있는 Pacific 바다로

모두 흐르는 좌표를 체킹하는 접근법이 떠오르지 않아서 레퍼런스를 참고했다.

그 결과 다시 세운 핵심전략은,

1. 시작좌표를 각 바다와 인접한 좌표들로만 배열을 구성한다. (Pacific, Atlantic 나눠서)
2. 파이썬의 set() 을 사용
    - Pacific으로 흐를 수 있는 좌표들의 set(),  Atlantic으로 흐를 수 있는 좌표들의 set() 을 따로 구하기.
        => 따로 BFS시행해야겠지
    - BFS 내에서도 visited라는 set()을 활용. 바다와 인접한 스타트 좌표들을 전부삽입.
        그리고 BFS를 통해 조건에 부합하여 큐에 삽입될때마다(방문할 때마다) 삽입  
3. 구한 집합들의 교집합을 구하면 된다. (set문법 활용)

리트코드는 다른 알고리즘 플랫폼들과 달리 이렇게 본인이 푼 솔루션의 시간복잡도, 공간복잡도 랭킹(?)도 알 수 있다.

코드

from collections import deque

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]    #동, 서 남, 북
        m = len(heights)
        n = len(heights[0])
        pacific = set()		# pacific 바다로 흐를 수 있는 좌표들 집합
        atlantic = set()	# atlantic 으로 흐를 수 있는 좌표들 집합

        def bfs(starts):
            queue = deque(starts)
            visited = set(starts)

            while queue:
                curX, curY = queue.popleft()
                for dx, dy in d:
                    nx = curX + dx
                    ny = curY + dy

                    # 육지내에 속하고, 방문하지 않았고, 이전 셀의 높이보다 높아야함.
                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited and heights[nx][ny] >= heights[curX][curY]:
                        queue.append((nx, ny))
                        visited.add((nx, ny))
            
            return visited

        # 각 바다와 인접한부분의 좌표를 각 바다의 스타트 배열로 만든다.
        pStart = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)]
        aStart = [(m-1, i) for i in range(n)] + [(i, n-1) for i in range(m-1)]

        pacific = bfs(pStart)
        atlantic = bfs(aStart)
    
        return list(pacific & atlantic) # 교집합 구해서 리스트 변환.
        # 핵심 아이디어: BFS
    
        # for문 돌려서 각지점에서 BFS 전부 시행??
        # 아틀란틱 => 우, 하 / 패시픽 -> 좌, 상 인데 체크조건을 어떻게 잡아야할까??

문제링크

https://leetcode.com/problems/two-sum/description/

문제설명

num배열과 target이 주어지고

num배열 안에 있는 정수 중 두개의 합이 target이 되는 두 정수값의 인덱스를 출력하라고 한다.

문제풀이

브루트 포스를 활용하여 O(N^2) 시간복잡도로 풀수도 있지만

나는 투포인터를 사용하여 O(N)만에 풀었다. 정렬도 사용했으니 최종코드의 시간복잡도는 O(NlongN) 이겠다.

그리고 solution에는 해시테이블을 사용하여 푼 풀이도 있었다.

투포인터로 코드 구현할때

인덱스와 값을 묶어 튜플로 저장하는 과정에서 나는 직접 반복문을 돌려 추가하였다.

# for i in range(N):
    # arr.append((nums[i], i))  #(2, 0), (7, 1), (11, 2), (15, 3)

코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        i, j = 0, N-1

        copyNums = sorted(enumerate(nums), key = lambda x: x[1])
        
        while i < j:
            sumValue = copyNums[i][1] + copyNums[j][1]
            if sumValue < target:
                i += 1
            elif sumValue > target:
                j -= 1
            else:
                return [copyNums[i][0], copyNums[j][0]]