IT LAB

난이도 : medium 문제링크 2개의 integer 리스트 nums1, nums2와 숫자k가 주어진다 리스트는 non-decreasing order이다 합이 작은 순서대로 k 개의 두 배열의 원소로 구성된 pair들을 리턴하세요 1. 접근법 합이 작으려면, 작은 숫자부터 뽑아서 pair를 구성해야 함 최소힙 자료구조를 사용하여 pair를 만든다 2. 의사코드 // 좌표의 합을 가지고 오름차순한 우선순위 큐를 생성한다 PriorityQueue pq = new PriorityQueue( (a, b) -> (a[0] + a[1]) - (b[0] + b[1]) ); // pq에 원소들을 모두 넣고 for (int n1 : nums1) { for (int n2 : nums2) { pq.offer(new int[..

난이도 : medium 문제링크 int array인 nums와 int값인 k가 주어진다 nums 배열에서 k번째로 큰 값을 리턴하라 1. 접근법 유일한 값이 아닌, 중복된 값을 포함하여 리턴해야 함 최대 힙을 구현하여, k번째 pop된 값을 리턴하기 2. 의사코드 1. Heap 클래스 구현 public void push(int e) { arr[n++] = e; bubbleUp(n-1); } public void pop() { int top = arr[n-1]; arr[0] = top; n--; bubbleDown(0); return top; } private void bubbleUp(int i) { if (i가 0보다 작거나 같으면) return; int parentIdx = (i-1)/2; if (ar..

난이도 : 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..

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

난이도 : easy 문제링크 binary tree의 root 노드가 주어짐 각 레벨의 평균값에 대한 list를 리턴하라 1

난이도 : 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)..

난이도 : 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..

난이도 : easy 문제링크 Binary Search Tree의 root 노드가 주어진다 노드들중 가장 작은 차이값을 리턴하라 노드의 수는 2~10^4 범위내에 있다 0

난이도 : 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..

난이도 : medium 문제링크 링크드리스트의 head가 주어짐 오름차순으로 정렬된 링크드리스트 참조객체를 리턴하라 node 갯수 : [0, 5 * 104] -105