본문 바로가기

전체 글26

105. Construct Binary Tree from Preorder and Inorder Traversal 문제 int[] 형 배열로 전위순회(preorder), 중위순회(inorder) 값이 주어졌을때 Binary Tree 를 만드는 문제이다. int[] preorder = {3, 9, 20, 15, 7}; int[] inorder = {9, 3, 15, 20, 7}; TreeNode node = [3, 9, 20, null, null, 15, 7]; 문제 풀이 전위순회, 중위순회, 후위순회 중 2가지 이상이 있다면 트리를 생성할 수 있다. 먼저 전위순회가 기준이 된다. 전위순회의 원소를 하나씩 가지고 와서 중위순회에 몇번째에 위치한지 인덱스를 찾는다. 이 인덱스가 루트노드가 되고, 해당 인덱스 기준으로 왼쪽이 왼쪽 자식노드들이 되고, 해당 인덱스 기준으로 오른쪽이 오른쪽 자식노드들이 된다. 예를 들어, 아.. 2023. 12. 26.
146. LRU Cache 문제 int 타입의 key, value 가 들어오고 저장하고나서 capacity (용량)이 초과된 경우, 가장 오래 사용하지 않은 값을 제거하는 lru 캐시를 구현하는 문제다. 풀이 이 문제는 LinkedHashMap 을 이용해서 풀수도 있고, 직접 linkedList 를 이용해서 풀 수도 있다. 코드 class LRUCacheMapClass { private Map map; public LRUCacheMapClass(int capacity) { this.map = new LinkedHashMap(capacity, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > capacity; .. 2023. 12. 24.
86. Partition List 문제 linked list 와 특정 값 x 가 주어졌을때 linked list 의 원소가 x 보다 작다면 왼쪽으로 x 보다 크다면 오른쪽으로 옮기는 문제다. 만약 x=3 이라면 아래와 같이 3보다 작은 원소는 왼쪽에 배치되고 3보다 큰 원소들은 오른쪽으로 배치된다. 이때 중요한건 기존 원소들의 정렬은 변경되면 안된다. 변경 전 1 -> 4 -> 3 -> 2 -> 5 -> 2 변경 후 1 -> 2 -> 2 -> 4 -> 3 -> 5 문제 풀이 x 값보다 작은 원소, 큰 원소를 구분지어서 저장하기 위한 small, big 을 추가로 생성한 뒤, small 원소와 big 원소를 합친 결과를 리턴하면 된다. x 보다 작은 원소들은 small 에 계속해서 추가되고, x 보다 큰 원소들은 big 에 계속해서 추가된.. 2023. 12. 23.
61. Rotate List 문제 개요 leetcode 의 Rotate List 문제로 linked list 가 주어지면 k 의 수 만큼 오른쪽으로 head 를 옮겨야 한다. 예를 들어 아래와 같은 linked list 가 있고 k = 2 일때는 아래와 같다. k=0) 1 -> 2 -> 3 -> 4 -> 5 -> nil k=1) 5 -> 1 -> 2 -> 3 -> 4-> nil k=2) 4 -> 5 -> 1 -> 2 -> 3-> nil 문제 풀이 문제의 제약조건을 보면 k 의 수가 최대 20억 이하까지 나올 수 있다. 단순 반복문으로 풀면 당연히 시간 초과할것 같았지만 처음에는 신경쓰지 않고 풀었다. 당연히 특정 테스트케이스에서 시간 초과가 났다. 해당 문제는 배열이 아닌 linked list 문제이기 때문에 원소의 개수를 구하기 .. 2023. 12. 23.

티스토리툴바