greentea31's Note

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

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

풀이 과정

원형 큐를 구현하는 문제이다.

선형 큐를 직접 구현시 front, rear 변수를 두고 구현했었는데 이는 큐의 사이즈 만큼 push()가 이루어지면 pop으로 큐를 다 비워도 추가로 원소를 넣을 수 없는 문제점이 있었다. 그래서 front, rear 변수가 큐의 크기를 넘어가면 큐의 크기로 나눈 나머지 값을 사용하게 해서 이미 변수가 채워졌다 없어진 공간도 다시 재활용이 가능하게 구현하였다.

소스 코드

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None for _ in range(k)]
        self.maxlen = k
        self.front = 0
        self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.q[self.rear] is None:
            self.q[self.rear] = value
            self.rear = (self.rear + 1) % self.maxlen
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.q[self.front] is None:
            return False
        else:
            self.q[self.front] = None
            self.front = (self.front + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return self.q[self.front] if self.q[self.front] is not None else -1

    def Rear(self) -> int:
        return self.q[self.rear - 1] if self.q[self.rear - 1] is not None else -1

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.q[self.front] is None
 
    def isFull(self) -> bool:
        return self.front == self.rear and self.q[self.front] is not None

https://leetcode.com/problems/implement-queue-using-stacks/

풀이 과정

스택을 사용해 큐를 구현하는 문제이다.

큐를 스택으로 구현하는데엔 2개의 스택이 필요하다. push때는 스택에 넣고, pop이나 맨 위의 원소를 뽑아야 할 때는 스택의 원소를 다른 스택에 모두 넣어서 스택의 원소의 순서를 모두 뒤집고 스택 탑에 접근해서 큐를 구현할 수 있다.

소스 코드

class MyQueue:
    def __init__(self):
        self.st = []
        self.st2 = []

    def push(self, x: int) -> None:
        self.st.append(x)

    def pop(self) -> int:
        self.peek()
        return self.st2.pop()

    def peek(self) -> int:
        if not self.st2:
            while self.st:
                self.st2.append(self.st.pop())
        return self.st2[-1]

    def empty(self) -> bool:
        if len(self.st) == 0 and len(self.st2) == 0:
            return True
        else:
            return False

https://leetcode.com/problems/implement-stack-using-queues/

풀이 과정

큐로 스택을 구현하는 문제이다. 큐 2개로 스택을 구현하라고 하고 있고, 후속조치로 큐 1개로 스택을 구현해달라고 하고 있다.

1. 큐 2개로 구현하기

pop 할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막에서 나오는 값일 것이므로, push 받을 때는 입력받은 값을 그냥 큐에 넣어주면 된다. pop 받을 때는 큐의 길이 - 1만큼 다른 큐에 원소들을 빼고 마지막 하나 남은 값을 pop 해주면 된다. top을 받았으면 마지막 하나 남은 값을 반환해주고 다시 큐에 넣어주면 된다. 스택이 비어있는지 판단하려면 큐 2개가 전부 비어있으면 스택도 비어있는 것이고, 아니면 스택에 원소가 있는 것이다.

2. 큐 1개로 구현하기

pop할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막으로 나오는 값임을 생각하며 그냥 push 받을 때 push 받은 값이 큐의 맨 앞으로 가게 조작해주면서 스택의 기능을 하게 할 수 있다. 일단 입력받은 값을 큐에 넣고 큐의 사이즈 - 1번만큼을 앞에서 빼준 다음에 다시 뒤에 붙여주면 된다.

예시)

1, 2, 3이라는 큐에서 4를 입력받으면

1, 2, 3 -> 1, 2, 3, 4 -> 2, 3, 4, 1 -> 3, 4, 1, 2 -> 4, 1, 2 3

pop()하면 4가 나올 것이고 나중에 입력받으면 먼저 나오는 스택이 구현됨.

소스 코드

큐 1개로 구현한 코드이다.

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]
        

    def empty(self) -> bool:
        return True if len(self.q) == 0 else False

https://leetcode.com/problems/daily-temperatures/

풀이 과정

각 날짜의 온도가 주어질 때, 어떤 날짜에서 며칠을 기다려야 더 따뜻한 날이 되는지 출력하는 문제이다.

2중 for문 돌려서 O(N^2)로도 해결할 수 있겠지만, 스택을 활용해서 더 효율적으로 문제를 해결할 수 있다.

수의 index를 스택에 저장하면서, 스택탑의 index 날짜의 온도보다 더 따뜻한 날의 index가 들어오면 스택을 pop하면서 따뜻한 날의 index - 스택 탑의 index를 계산해서 정답 리스트에 저장해주면 문제를 해결할 수 있다. 

소스 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        answer = [0 for _ in range(len(temperatures))]
        for a, b in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < b:
                last = stack.pop()
                answer[last] = a - last
            stack.append(a)
        return answer

https://leetcode.com/problems/remove-duplicate-letters/

풀이 과정

중복된 문자를 제거하되, 문자열을 사전식 순서로 나열하는 문제이다.

문제가 약간 이해하기 어려운데 set으로 중복 문자 없애고 sort로 정렬하라는 소리인가? 싶긴 하지만 예시를 보면 그렇지 않다. 2번 예시를 보자.

"cbacdcbc"가 예시로 주어져 있는데 여기에 단순히 ''.join(sorted(set(s))) 를 하게 되면 답이 'abcd'가 나오게 된다. 하지만 이 문제에서 원하는 정답은 acdb로 중복을 제거할 때 어떤 문자를 지우는지로 사전식 순서를 맞추되 문자의 위치를 옮기지는 않는 그런 방식을 요구하고 있다. 중복된 문자를 어떤 것을 지우는지에 따라 나올수 있는 것이 ['cbad', 'bacd', 'acbd'..]의 다양한 결과가 나올 수 있는데 이 중에서 사전식 순서로 맨 앞에 나와있는 것은 'acbd'니까 이것을 출력하라는 것이다.

사전상 앞에 있는 알파벳의 index를 찾고 거기서 문자열을 분리하고, 분리한 문자열에서 중복을 제거한 것이 원래 문자열에서 중복을 제거한 것과 같으면 정답에 분리 기준 문자를 추가하고... 를 재귀식으로 반복하는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''