IT LAB

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

난이도 : easy 문제링크 정수형 배열이 주어짐 두개의 수를 조합하여 더한 값이 target이 되는 두 수를 리턴하라 오직 한번씩만 사용해야 함 (중복 불가) 출력 순서는 상관없음 2

난이도 : 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의 크기가 잡힐..