본문 바로가기

top-interview-15016

LeetCode : 133. Clone Graph 문제 링크 문제 먼저 읽기 연결된 방향이 없는 그래프에서 노드의 참조가 주어집니다. 깊은 복사를 한 그래프를 반환하세요. 어떻게 풀까? 생각 이웃을 순회하면서 재귀로 해결하는 것을 시도해보았습니다. 수도코드 class Solution { public Node cloneGraph(Node node) { ArrayList neighbors = new ArrayList(); boolean[] visit = new boolean[101]; for (int i=0; i 2023. 9. 15.
LeetCode : 211. Design Add and Search Words Data Structure 문제 링크 문제 먼저 읽기 새 단어를 추가하거나 추가한 단어와 일치하는 문자열을 찾을 수 있는 데이터 구조를 구현해봅시다. WordDictionary() 객체를 초기화합니다. void addWord(word) 데이터 구조에 단어를 추가하며, 나중에 일치시킬 수 있습니다. void search(word) 데이터 구조에 단어와 일치하는 문자열이 있으면 참을 반환하고 그렇지 않으면 거짓을 반환합니다. 단어는 점 '.'을 포함할 수 있으며, 여기서 점은 어떤 문자와도 일치할 수 있습니다. 어떻게 풀까? 생각 Trie 를 다시한번 구현해봅시다. 어제 풀었던 문제라 생각보다 바로 수도코드를 작성할 수 있었습니다. . 이 나오는 경우에는 모든 문자를 검색할 수 있도록 합니다. 수도코드 class WordDiction.. 2023. 9. 12.
LeetCode : 208. Implement Trie (Prefix Tree) 문제 링크 문제 먼저 읽기 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, .. 2023. 9. 11.
LeetCode : 230. Kth Smallest Element in a BST 문제 링크 문제 먼저 읽기 이진 검색 트리의 루트와 정수 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.. 2023. 9. 8.
LeetCode : 530. Minimum Absolute Difference in BST 문제 링크 문제 먼저 읽기 이진 검색 트리(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.. 2023. 9. 8.
LeetCode : 148. Sort List 문제 링크 문제 먼저 읽기 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)이 될 것으로 예상됩니다. 새로운 리스트에 값을.. 2023. 9. 5.
LeetCode : 155. Min Stack 문제 링크 문제 먼저 읽기 푸시, 팝, 탑, 최소 요소 검색을 일정 시간 내에 지원하는 스택을 구현하시오. 어떻게 풀까? 생각 ArrayList 혹은 int[]로 구현해볼 수 있다. 수도코드 class MinStack { private List stack; private List minStack; // 최소값 저장 스택 public MinStack() { // 스택 초기화 this.stack = new ArrayList(); this.minStack = new ArrayList(); } public void push(int val) { if (stack.size() == 0) { // 첫요소일 때. 처음에 이부분을 생각하지 못해서 emptyStackException이 발생했었다. this.minStack.. 2023. 9. 1.
LeetCode : 150. Evaluate Reverse Polish Notation 문제 링크 문제 먼저 읽기 문자 배열이 주어집니다. 문자는 각각 사칙 연산 1글자씩이거나 숫자인데 Reverse Polish Notation (후위 표기법)산술식을 나타냅니다. 연산의 결과를 반환하세요. Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 그 외 조건 1 2023. 8. 31.

티스토리툴바