분류 전체보기 558

[Leetcode Top Interview 150] 211. Design Add and Search Words Data Structure

난이도 : medium 문제링크 단어 추가, 찾기의 기능을 가진 자료구조를 구현하라 찾기 : '.' 문자 사용 가능 (와일드카드) word 1 return false } List tmp; for (entry : node.children.entrySet()) { tmp.add(search(entry.getValue(), word.substring(1)); } return !tmp.stream().allMatch(b -> b == false); } return search(node.children.get(word의 첫번째 단어), word.substring(1)); } 3. 구현 코드 class WordDictionary { class Node { private Map children; private boo..

Algorithm/(Java) PS 2023.09.11

[Leetcode Top Interview 150] 208. Implement Trie (Prefix Tree)

난이도 : medium 문제링크 trie (or prefix tree)는 문자열 데이터셋의 키를 저장하거나 가져오는데 효과적인 트리자료구조 이다 맞춤법 체크나 자동완성 기능의 구현에 사용된다 insert(), search(), startWith() 메서드를 구현하세요 1. 접근법 문자열들은 문자들의 순차적으로 의존하는 데이터 하나의 문자를 노드로 생성함 각 노드는 자식의 정보를 담은 Map 자료구조와 해당 글자까지 단어인지 여부를 가지는 boolean 필드를 가진다 Trie 자료구조는 트리를 순회하는데 사용하기 위한 Node 타입의 root라는 필드를 가지도록 함 insert(String word) 파라미터로 받은 word의 부분문자열이 tree에 이미 존재한다면 tree에서 부분문자열의 마지막 node..

Algorithm/(Java) PS 2023.09.11

[Leetcode Top Interview 150] 199. Binary Tree Right Side View

난이도 : medium 문제링크 root로부터 오른쪽 측면에서 보았을때 보이는 노드들을 출력하라 1. 접근법 해당 노드 전부를 전위표현식으로 방문하여 리스트에 집어넣음 그리고 오른쪽부터 방문하면서 해당 레벨에서 존재하는 가장 오른쪽 노드를 리스트의 인덱스로 찾아냄 방문하면서 answer 배열에 가장 오른쪽 노드 값을 집어넣음 2. 의사코드 dfs(root); Queue queue = new LinkedList(); queue.offer(root); while (queue.isEmpty()) { // depth 별 answer를 구한다 } public void dfs(TreeNode root) { if (root == null) { return; } list.add(root); dfs(root.right)..

Algorithm/(Java) PS 2023.09.06

[Leetcode Top Interview 150] 230. Kth Smallest Element in a BST

난이도 : medium 문제링크 binary search tree의 root 노드와 int k 값이 주어진다 k번째로 작은 값의 노드를 리턴하라 1. 접근법 중위표현식으로 탐색하면 오름차순으로 탐색이 가능하다 k번째 값을 리턴 2. 의사코드 count = 0; if (count == k) { return root.val; } int ans = Dfs(root.left); if (ans != Integer.MAX_VALUE) { return ans; } count++ if (count == k) { return root.val; } return Dfs(root.right); 3. 구현 코드 class Solution { int count = 0; public int kthSmallest(TreeNode r..

Algorithm/(Java) PS 2023.09.06

[Leetcode Top Interview 150] 162. Find Peak Element

난이도 : medium 문제링크 peak element : 이웃보다 큰 노드 peak element의 인덱스를 리턴하라 peak element는 복수개가 될 수 있으나, 어느것중 하나만 정확하게 리턴하라 시간복잡도 O(logn) 성능의 알고리즘을 작성하라 1 left) { mid = (right + left)/2 + 1; if (nums[mid] > nums[mid-1]) { left = mid; } else { right = mid-1; } } return right; } } 투포인터를 두고, 각 포인터의 중간값과 중간값의 직전값을 비교함 중간값이 크다면, 가장 큰 값의 인덱스 범위는 mid ~ right 안에 있으므로 left를 mid로 변경 중간값의 직전값이 크다면, 가장 큰 값의 인덱스 범위는 l..

Algorithm/(Java) PS 2023.09.05

[Leetcode Top Interview 150] 150. Evaluate Reverse Polish Notation

난이도 : medium 문제링크 tokens이라는 String 배열이 주어짐 후위표기식으로 표현되는 배열 결과를 리턴하라 결과의 범위는 32bit division by zero 없음 -200 left - right; case "*" -> left * right; case "/" -> left / right; default -> 0; }; } } stack에서 먼저 뽑은 operand가 right operand (더 늦게 들어갔음) stack에서 나중에 뽑은 operand가 left operand (더 빨리 들어갔음) 4. 시간복잡도, 공간복잡도 예상 시간복잡도 : O(n) - tokens의 길이만큼 반복하면서 연산함 공간복잡도 : O(n) - 최대 tokens의 원소갯수의 반만큼 stack의 크기가 잡힐..

Algorithm/(Java) PS 2023.09.01