greentea31's Note

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

풀이 과정

주어진 리스트의 순열을 구하는 문제이다.

itertools 모듈의 permutation 함수를 사용하면 문제를 쉽게 해결할 수 있다. 또한, DFS로도 순열을 생성할 수 있다.

https://greentea31.tistory.com/110?category=939228 

위의 재귀로 순열을 구현하는 예제가 일종의 dfs - backtracking으로 순열을 구현한 것이다.

재귀 1의 소스코드에서, answer.append(output)을 사용하면 맨 마지막 output이 중복 저장되므로

1. answer.append(output[:])

2. answer.append([i for i in output])

3. import copy

    answer.append(copy.deepcopy(output))

등을 이용해주어야 한다.  위의 2방법은 객체 내의 내부 객체까지는 복사되지 않는 반면, deepcopy를 사용하면 깊은 복사가 되어 내부 객체까지 완벽히 복사된다. 이 문제에서는 리스트 내의 리스트까지 존재하지는 않으므로 위의 2방법을 사용해도 된다.

소스 코드

재귀 1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        output = [-1 for _ in range(length)]
        answer = []
        discovered = collections.defaultdict(bool)
        
        def go(index, length):
            if index == length:
                answer.append(output[:])  # answer.append(output) 사용시 맨 마지막 output값 중복 저장됨.
                return
            
            for num in nums:
                if not discovered[num]:
                    discovered[num] = True
                    output[index] = num
                    go(index+1, length)
                    discovered[num] = False
        
        go(0, length)
        return answer

재귀 2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []  # 이미 순열에 넣은 원소의 집합
        
        def dfs(elements):
            if len(elements) == 0:  # 모든 원소를 다 넣었으면 결과 값에 넣는다.
                results.append(prev_elements[:])
                # [:]가 없으면 prev_elements가 변경되면서 results에 들어갔던 값들도 변경된다.
            
            for ele in elements:
                prev_elements.append(ele)
                #  next_elements는 앞으로 순열에 넣어야 할 원소의 집합
                next_elements = elements[:]
                next_elements.remove(ele)
                
                dfs(next_elements)
                prev_elements.pop()
        
        dfs(nums)
        return results

itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

풀이 과정

숫자 문자열이 주어졌을때 문자열의 각 숫자로 만들수 있는 알파벳 조합을 리턴하는 문제이다.

'234'가 주어졌다고 가정하면 2에서 a고르고 3으로 넘어가고, b고르고 3으로 넘어가고, c고르고 3으로 넘어가고... 이러한 방법을 반복해주다가 숫자 문자열의 길이와 내가 고른 알파벳 문자열의 길이가 같아지면 정답 배열에 알파벳 문자열을 추가해주면 된다.

일종의 dfs backtracking 문제이다. 숫자 문자열의 길이보다 작은 길이의 알파벳 문자열을 만드는 문제였으면 특정 숫자를 사용할지 사용하지 않을지 고르는 부분도 추가되어야 했을 것이다.

재귀를 사용해 구현하였다.

소스 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        answer = []
        
        def combi(index, discovered=""):
            if len(discovered) == len(digits):
                if digits:
                    answer.append(discovered)
                return
            for i in dic[digits[index]]:
                combi(index+1, discovered + i)

        combi(0)
        return answer

https://leetcode.com/problems/number-of-islands/

풀이 과정

지도에서 땅으로 연결된 섬의 개수를 찾는 문제이다.

그래프에서 연결 요소를 찾으라는 문제인데, 지도의 모든 칸에 대해 dfs 혹은 bfs로 방문하면 연결요소의 개수를 찾을 수 있다.

보통 visited 이차원 배열을 선언해서 이전에 방문했는지를 판별하는데, 이 문제는 이차원 배열을 선언하지 않고 이미 방문한 땅을 물로 바꿔주면 방문했던 곳을 다시 방문하는 것을 막을 수 있다. 이러면 메모리 효율성이 증가한다.

지도를 보면서 땅인 부분을 bfs로 방문하고, 정답 변수를 1 증가시켜주고, 방문한 땅 및 그와 연결된 땅을 전부다 물로 바꿔주는 방법으로 문제를 해결할 수 있다.

bfs를 중첩 함수로 만들고 지도에서 땅인 부분을 방문하게끔 하였다.

소스 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        answer = 0
        def bfs(start_y, start_x):
            grid[start_y][start_x] = 0
            Q = collections.deque([[start_y, start_x]])
            while Q:
                v = Q.popleft()
                for i in range(4):
                    ny = v[0] + dy[i]
                    nx = v[1] + dx[i]
                    if 0 <= ny < m and 0 <= nx < n and grid[ny][nx] == "1":
                        Q.append([ny, nx])
                        grid[ny][nx] = 0
                        
                        
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    bfs(i, j)
                    answer += 1
        return answer

https://leetcode.com/problems/top-k-frequent-elements/

풀이 과정

배열에서 가장 많이 출현한 원소를 k개 반환하는 문제이다.

파이썬에서는 collections 모듈의 Counter 클래스를 사용해 리스트에서의 원소의 개수를 쉽게 구할 수 있다.

a = [1, 3, 2, 2, 4]

b = collections.Counter(a) = Counter({2: 2, 1: 1, 3: 1, 4: 1})

c = b.most_common() = [(2, 2), (1, 1), (3, 1), (4, 1)]

c = b.most_common(2) = [(2, 2), (1, 1)]

위와 같이 활용된다.

Counter 클래스를 활용해 문제를 해결하였다.

소스 코드

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        ans = collections.Counter(nums).most_common(k)
        answer = []
        for i in (ans):
            answer.append(i[0])
        return answer

https://leetcode.com/problems/longest-substring-without-repeating-characters/

풀이 과정

문자열을 입력받고 반복되는 문자가 없는 가장 긴 부분 문자열을 구하는 문제이다.

2중 for문으로 문자열을 읽으면서 문자를 딕셔너리에 넣고, 새로운 문자가 이전에 나왔는지 확인하면서 길이 변수를 1씩 늘려가는 방법으로도 풀이가 가능하다. O(N^2)으로 풀이가 되기는 하는데 풀고 나면 수행 시간 순위가 바닥임을 확인할 수 있다.

투 포인터로 O(N)에 해결이 가능하다.

문자열을 읽으면서 각 문자가 마지막으로 나온 위치를 used 딕셔너리 (26칸의 크기로 가진 배열로 처리해도 된다.)에 저장하고, 문자가 이전에 출현한 적이 있고, 투포인터의 시작 지점이 문자의 이전 출현 점보다 같거나 이전이면 같은 문자가 2번 이상 나온 것이므로 시작 지점을 1 늘려주고, 아니면 길이와 투포인터의 끝 지점을 갱신하는 방법으로 문제를 해결할 수 있다.

아래 제출 코드는 2중 반복문이고, 위 제출 코드는 투 포인터이다. 실행시간 차이가 20배 넘게 난다. 2중 반복문으로는 해결이 되긴 하지만 비효율적인 풀이이니 투 포인터를 이용해야 한다.

소스 코드

2중 반복문

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        for i in range(len(s)):
            length = 0
            dic = collections.defaultdict(int)
            for j in range(i, len(s)):
                if dic[s[j]] == 1:
                    break
                dic[s[j]] = 1
                length += 1
                answer = max(length, answer)
        return answer

투 포인터

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_len = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_len = max(max_len, index - start + 1)
            used[char] = index
        return max_len

https://leetcode.com/problems/jewels-and-stones/

풀이 과정

보석 문자열과 돌 문자열을 받아서 돌 문자열 안에 보석이 몇 개 들어있는지 구하는 문제이다.

보석 문자를 딕셔너리에 저장하고, 돌 문자열을 읽으면서 딕셔너리에 있는 문자면 정답 변수를 1씩 늘려주는 방법으로 풀이하였다.

52개의 0으로 초기화 된 리스트를 선언 후, 보석 문자를 읽으면서 해당하는 index의 원소를 1로 바꿔주고, 다시 돌 문자를 읽으면서 배열 index 확인하며 정답 변수를 1씩 늘리는 방법으로도 해결이 가능하다.

소스 코드

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        diction = collections.defaultdict(int)
        answer = 0
        for letter in jewels:
            diction[letter] = 1
        for letter in stones:
            if diction[letter] == 1:
                answer += 1
        return answer

https://leetcode.com/problems/design-hashmap/

풀이 과정

built-in hash table libraries를 사용하여 HashMap을 구현하는 문제이다.

해시 테이블의 구현시, 서로 다른 값이 같은 해시값을 가지는 해시 충돌이 발생할 수 있다. 해시 충돌을 처리하는 방법은 크게 2가지가 있는데, 개별 체이닝(Separate Chaining) 방식과 오픈 어드레싱(Open Addressing) 방식이다.

1. 개별 체이닝

해시 값의 충돌이 발생하면 기존 해시 값에 배정되어 있는 노드의 뒤로 링크드 리스트 처럼 연결하는 방식이다.

2. 오픈 어드레싱

해시 값의 충돌이 발생하면 데이터가 저장되어 있지 않은 주소값을 찾아 해시 값 근처의 주소를 탐색해 배정하는 방식이다.

파이썬의 딕셔너리는 오픈 어드레싱 방식으로 구현되어 있다. 이 문제에서 HashMap을 구현할 때에는 개별 체이닝 방식을 사용하였다.

개별 체이닝시 노드의 연결을 위해 key, value, next 값을 갖는 노드를 설정해주었고, 해쉬 함수는 해쉬 맵 사이즈의 모듈러 연산을 사용하였다.

소스 코드

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.table = collections.defaultdict(ListNode)

    def put(self, key: int, value: int) -> None:
        index = key % self.size
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return
        node = self.table[index]
        while node:
            if node.key == key:
                node.value = value
                return
            if node.next is None:
                break
            node = node.next
        node.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.size
        if self.table[index].value is None:
            return -1
        node = self.table[index]
        while node:
            if node.key == key:
                return node.value
            node = node.next
        return -1

    def remove(self, key: int) -> None:
        index = key % self.size
        if self.table[index].value is None:
            return
        node = self.table[index]
        if node.key == key:
            self.table[index] = ListNode() if node.next is None else node.next
            return
        prev = node
        while node:
            if node.key == key:
                prev.next = node.next
                return
            prev, node = node, node.next

https://school.programmers.co.kr/learn/courses/30/lessons/62048

풀이 과정

격자 칸 1cm*1cm로 이루어진 w cm, h cm의 직사각형을 대각선으로 찢을때 사용 가능한 1cm*1cm 사각형의 면적을 구하는 문제이다.

다른 사람들의 코드를 보면 w*h-(w+h-gcd(w,h)) 라는 식으로 많이 풀었던데 풀이가 와닿지 않아서 대각선을 일차 함수로 생각하여 해결하였다.

w = 8, h = 12일때 y = 3/2x 라는 직선 밑에 있으면서 직선과 겹치지 않은 사각형의 개수를 구한 뒤, 2배를 해주어 답을 구하였다.

파이썬으로 풀이시 시간초과가 발생하므로 파이썬으로 문제 풀이시에는 w*h-(w+h-gcd(w,h)) 라는 식으로 문제를 해결해야 한다.

소스 코드

using namespace std;

long long solution(int w, int h) {
    long long answer = 0;

    for (int i = 0; i < w; i++) {
        answer += int((double)h*i/w);
    }

    return 2 * answer;
}

https://leetcode.com/problems/merge-k-sorted-lists/

풀이 과정

k개의 오름차순으로 정렬되어 있는 링크드 리스트를 입력받아 1개의 오름차순 정렬 링크드 리스트를 반환하는 문제이다.

우선순위 큐를 이용하여 문제를 해결하였다. heapq 모듈을 사용하였는데 heapq는 최소 힙을 구현한 모듈이다. (노드 값, 인덱스, 링크드 리스트) 튜플을 최소 힙에 다 넣고 최소 힙에서 나오는 순서대로 연결 순서를 조절해 줌으로써 하나의 링크드 리스트로 통합하였다.

튜플에서 인덱스 값은 필요가 없는 값인데, 튜플 (a, b, c), (d, e, f)를 heap에 heappush시에 a와 d를 비교해서 작은 값 -> 같으면 b와 e를 비교해서 작은 값 -> 같으면 c와 f를 비교해서 작은 값이 힙에서 위로 가게끔 한다. 그런데 인덱스 값을 쓰지 않으면 노드 값이 같은 두 링크드 리스트의 튜플 (노드 값 1, 링크드 리스트 1), (노드 값 2, 링크드 리스트 2)을 비교할 때 노드 값 1 == 노드 값 2 이므로 링크드 리스트 1, 링크드 리스트 2를 비교하게 하는데 링크드 리스트 1 < 링크드 리스트 2 같은 연산은 정의되어 있지 않아서 오류가 발생한다.

그래서 (노드 값 1, 인덱스 값 1, 링크드 리스트 1), (노드 값 2, 인덱스 값 2, 링크드 리스트 2) 같이 lists 내의 인덱스 값을 튜플에 추가해서 노드 값이 같으면 lists에서 먼저 나온 링크드 리스트가 최소 힙의 루트 쪽에 가깝게 배열되게 설정한 것이다.

소스 코드

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        root = res = ListNode(None)
        heap = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))
        
        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            res.next = node[2]
            res = res.next
            
            if res.next:
                heapq.heappush(heap, (res.next.val, idx, res.next))
        
        return root.next

https://leetcode.com/problems/design-circular-deque/

풀이 과정

원형 덱을 구현하는 문제이다.

left, right 포인터를 가진 양방향 링크드 리스트로 구현하였고, head 노드와 tail 노드는 실제로 값을 가진 노드를 가리키는게 아닌 덱의 맨 앞과 맨 뒤를 접근하기 위한 노드로 구현하였다.

실제 덱의 맨 앞의 값을 조회하려면 head.right.val로 조회하여야 하고, 맨 뒤의 값을 조회 하려면 tail.left.val로 조회하여야 한다.

소스 코드

class MyCircularDeque:
    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head
        
    def add_node(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new
        
    def del_node(self, node: ListNode):
        n = node.right.right
        node.right, n.left = n, node

    def insertFront(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self.add_node(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self.add_node(self.tail.left, ListNode(value))
        return True
        

    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self.del_node(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self.del_node(self.tail.left.left)
        return True

    def getFront(self) -> int:
        return self.head.right.val if self.len else -1

    def getRear(self) -> int:
        return self.tail.left.val if self.len else -1

    def isEmpty(self) -> bool:
        return self.len == 0        

    def isFull(self) -> bool:
        return self.len == self.k