문제 링크 문제 먼저 읽기 연결된 방향이 없는 그래프에서 노드의 참조가 주어집니다. 깊은 복사를 한 그래프를 반환하세요. 어떻게 풀까? 생각 이웃을 순회하면서 재귀로 해결하는 것을 시도해보았습니다. 수도코드 class Solution { public Node cloneGraph(Node node) { ArrayList neighbors = new ArrayList(); boolean[] visit = new boolean[101]; for (int i=0; i

문제 링크 문제 먼저 읽기 새 단어를 추가하거나 추가한 단어와 일치하는 문자열을 찾을 수 있는 데이터 구조를 구현해봅시다. WordDictionary() 객체를 초기화합니다. void addWord(word) 데이터 구조에 단어를 추가하며, 나중에 일치시킬 수 있습니다. void search(word) 데이터 구조에 단어와 일치하는 문자열이 있으면 참을 반환하고 그렇지 않으면 거짓을 반환합니다. 단어는 점 '.'을 포함할 수 있으며, 여기서 점은 어떤 문자와도 일치할 수 있습니다. 어떻게 풀까? 생각 Trie 를 다시한번 구현해봅시다. 어제 풀었던 문제라 생각보다 바로 수도코드를 작성할 수 있었습니다. . 이 나오는 경우에는 모든 문자를 검색할 수 있도록 합니다. 수도코드 class WordDiction..

문제 링크 문제 먼저 읽기 Trie 를 구현하세요 Trie() trie를 초기화합니다. void insert(String word) 를 insert 합니다. boolean search(String word) word가 있으면 true, 없으면 false를 반환합니다. boolean startsWith(String prefix) 이미 존재하는 단어중에 prefix로 시작하는 단어가 있으면 true, 아니면 false를 반환합니다. Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, ..

문제 링크 문제 먼저 읽기 이진 검색 트리의 루트와 정수 k가 주어졌습니다. 트리에 있는 모든 노드의 값 중 K번째 가장 작은 값(1-indexed)을 반환합니다. 어떻게 풀까? 생각 root로부터 맨 왼쪽에 위치한 값이 제일 작은 값입니다. 거기서부터 시작해서 이전 노드, 오른쪽 노드 순서대로 탐색할 수 있는 재귀함수를 만듭니다. 수도코드 class Solution { int count = 0; int result = 0; public int kthSmallest(TreeNode root, int k) { count = k; search(root); return result; } public void search(TreeNode node) { if (node == null) return ; search..

문제 링크 문제 먼저 읽기 이진 검색 트리(BST)의 루트가 주어졌을 때, 트리에 있는 서로 다른 두 노드의 값 사이의 최소 차이 절대값을 반환합니다. Input: root = [1,0,48,null,null,12,49] Output: 1 어떻게 풀까? 생각 주의! 처음에 문제를 잘못읽었었습니다. 역시 사람의 언어를 가장 잘해야 합니다 🥲 트리는 정렬 규칙상 인접 노드가 가장 그 차이가 적습니다. 그래서 인접하는 노드끼리 비교하면 안될까요? 재귀를 통해 BST 를 구현해봅시다. 수도코드 class Solution { TreeNode prev = null; int min = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { search..

문제 링크 문제 먼저 읽기 linkedlist의 head인 ListNode가 하나 주어집니다. 이 리스트를 오름차순으로 정렬하고 head를 반환합니다. 시간복잡도 O(nlogN), 공간복잡도 O(1)의 답변이 있는 모양입니다 🫠 Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)? 어떻게 풀까? 생각 처음 문제를 읽고 좀 당황했습니다. linked list를 정렬을 다시 해본적이 없었기 때문입니다. 가장 먼저 든 생각은 새로운 LinkedList를 만들어서 이전 리스트를 탐색함과 동시에 새로운 리스트에 값을 넣어주는 것입니다. 이 경우 시간복잡도는 O(n^2)이 될 것으로 예상됩니다. 새로운 리스트에 값을..