IT LAB

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

난이도 : medium 문제링크 push, pop, top, getMin 메서드를 구현하라 모든 메서드의 시간 복잡도는 O(1)여야 함 2^(-31)

난이도 : medium 문제링크 두개의 링크드 리스트가 주어짐 음이 아닌 정수로 이루어짐 각 링크드 리스트는 역순으로 데이터가 표현됨 0을 시작으로 하는 데이터는 존재하지 않음 두개의 링크드 리스트 합을 표현한 링크드리스트를 리턴하라 링크드리스트의 길이 : 1~100 1. 접근법 l1과 l2의 next가 null이 될 때까지 반복 next에 새로운 노드를 붙임 반복 횟수별 노드를 생성하여 val값을 합으로 만듬 2. 의사코드 int carry = 0; ListNode ans = new ListNode(); int sum = 0; while (l1 혹은 l2이 null이 아니면) { ans.val = l1.val + l2.val + carry; if (ans.val >= 10) { ans.val -= 10..

난이도 : easy 문제링크 링크드리스트의 사이클 여부를 리턴하라 1. 접근법 head로 linked list를 순회하면서 hashSet의 값을 가리킨다면 사이클 2. 의사코드 Set hashSet = new HashSet(); while (head.next != null) { if (hashSet에 노드가 없다면) { hashSet에 노드 추가 } else { return true; } head 한칸 이동 } return false; 3. 구현 코드 public class Solution { public boolean hasCycle(ListNode head) { if (head == null) { return false; } Set hashSet = new HashSet(); while (head.n..

난이도 : medium 문제링크 반복되는 문자 없이 가장 긴 substring의 길이를 구하라 0