파이문

문제 설명 링크드 리스트가 주어지는데, 상수의 공간 복잡도와 O(nlogn) 의 시간 복잡도로 정렬하는 문제다. 코드는 여기서 확인 가능하다. 솔루션 꼼수 가장 쉬운 방법은 링크드 리스트를 배열로 만들어서 언어에 built-in 된 sort 함수를 사용하는 것이다. 참고로 python 은 timsort 라는 알고리즘으로 sort 가 구현되어 있다. 아니면 sort 함수 말고 직접 정렬을 구현하면 될 것 같다. 하지만 이러면 constant space complexity 를 만족할 수가 없다. 두뇌 풀가동 merge sort 로 하면 될 것 같았다. 이때 절반을 divide 해야 하는데 배열이랑 다르게 사이즈를 알 수가 없다. 이를 위해 fast-slow 로 노드를 순회한다. 이는 tortoise-hare..

문제 설명 HashMap 을 구현하는 문제다. Python 으로 풀었다. 전체 코드는 여기서 볼 수 있다. 솔루션 Java의 HashTable 구현과 비슷하게 풀었다. 리스트를 두고 key 와 리스트 사이즈간의 hash 값을 구해서 리스트의 인덱스로 사용하였다. 인덱스가 겹칠 경우 (hash collision) 링크드리스트로 노드를 만들어서 넣어두었다. class Node: def __init__(self, key=None, value=None): self.key = key self.value = value self.next = None def __str__(self): return "Node(key:%s, value:%s, next:%s)" % (self.key, self.value, self.next..

518. Coin Change 2(https://leetcode.com/problems/coin-change-2/#/description) amount 를 coins의 값들로 만들 수 있는 모든 경우의 수를 리턴하는 문제다. 원래는 coin들로 recursive 하게 빼주다가 0이 되면 리턴하게 하는 식으로 하려고 했는데, 빼주었던 coin들을 어떻게 가지고 있어야 할지 구현하는게 어려워서 포기했다. 결국 DP로 풀었는데, 2차원 배열로 어떻게 하려다가 잘 안되서 그냥 인터넷에서 보고 구현했다. dp의 index값은 amount 값이 되고, 그렇기에 0원을 만들 수 있는 경우의 수는 1가지 (아무것도 없는 경우) 있기 때문에 dp[0] = 1 을 해준 상태에서 시작한다. amount 5, coins = ..

540. Single Element in a Sorted Array(https://leetcode.com/problems/single-element-in-a-sorted-array/#/description) 어떤 List에 int 값이 들어있는데 하나의 숫자만 한개가 있고, 나머지는 모두 두개씩 있을 때, 그 하나만 존재하는 숫자를 리턴하는 것입니다. for문 두번 돌리면 간단히 해결하지만 조건이 붙었습니다. 공간 복잡도 O(1)에, 시간 복잡도가 (logN)입니다. logN이기 때문에 분할해야 하는데, 저는 재귀로 나누어가면서 풀었습니다.List의 정 가운데를 자른다고 생각하면 현재 숫자를 기준으로 왼쪽이 홀수개의 리스트면 왼쪽에 찾고자 하는 숫자가 있을 것이고 오른쪽이 홀수개의 리스트면 오른쪽에 있을..

101. Symmetric Tree(https://leetcode.com/problems/symmetric-tree/#/description) 대칭이 되는 트리인지 아닌지를 판별하는 문제입니다.아래와 같이 가운데(?) 를 기준으로 접혀진다면(대칭이 된다면) True를 리턴하고 1 / \ 2 2 / \ / \ 3 4 4 3한쪽이 비거나, 다른 숫자가 들어가거나 등등 대칭이 되지 않는다면 False를 리턴합니다. 1 / \ 2 2 \ \ 3 3 Easy 문제이기 때문에 어렵게 생각할 필요가 없습니다.문제 그대로 맨 왼쪽은 맨 오른쪽과 같아야 하고, 가장 왼쪽의 오른쪽은 (형제 노드는) 가장 오른쪽의 왼쪽 노드 (형제 노드)와 같으면 됩니다. 재귀로 계속 체크해나가면서, None이면 가장 끝의 노드이니 그 때..