Algorithm20 133. Clone Graph 문제 아래와 같은 변수를 가진 Node 클래스가 주어졌을때 해당 Node 클래스를 deep copy 하는 문제입니다. class Node { public int val; public List neighbors; } neighbors 값이 저장된 형태는 아래와 같습니다. 1 -> 2, 4 2 -> 1, 3 3 -> 2, 4 4 -> 1, 2 위 그림의 첫번째는 얕은 복사로 객체의 주소가 똑같은 경우 잘못된 결과이고, 세번째 그림은 neighbors 가 잘못되었습니다. 두번째 그림의 결과처럼 복사하여 리턴해야 합니다. 문제 풀이 재귀함수를 이용한 풀이와 Bfs 를 이용한 풀이가 있습니다. Bfs 풀이 bfs 풀이는 첫번째 노드를 기준으로 연관된 노드들을 큐에 넣고 꺼내면서 순회하며 map 을 만듭니다. 큐에.. 2024. 1. 9. 130. Surrounded Regions 문제 char 타입의 'O' 와 'X' 가 저장된 m x n 2차원 배열이 주어졌을때, 'X' 로 둘러싸인 'O' 를 'X' 로 변환하는 문제입니다. 만약 'O' 가 2차원 배열의 가장자리에 있다면 둘러쌓여 있지 않다고 보면 됩니다. 위와 같이 'O' 가 3개 붙어있지만 'X' 로 둘러 쌓여있으므로 'X' 로 바꿀 수 있습니다. 반면 (3, 1) 위치에 있는 'O' 는 가장 자리에 있으므로 'X' 로 바꿀 수 없습니다. 문제 풀이 Bfs, Dfs 2가지 방법으로 풀 수 있습니다. 2차원 배열 관련된 문제에서 특정 문자열을 찾거나 할때 보통 중첩 반복문을 돌립니다. 하지만 이 문제는 중첩 반복문을 돌리면 시간 초과가 나기 때문에 배열의 가장자리를 기준으로 왼쪽과 오른쪽 -> 윗쪽과 아래쪽 가장자리부터 'O.. 2024. 1. 7. 117. Populating Next Right Pointers in Each Node II 문제 Left, Right, Next 포인터를 가진 노드가 주어지면, 왼쪽에 있는 노드가 자신의 오른쪽 노드를 가리키도록 추가하는 문제입니다. 해당 문제는 완벽한 이진트리가 아니기 때문에 오른쪽 노드가 없다면, 그 다음 오른쪽 노드를 가리켜야 합니다. 위 그림의 5번 원소의 오른쪽은 비어있습니다. 하지만, 그 다음 오른쪽에 7 원소가 있기 때문에 7을 Next 포인터로 가리키면 됩니다. 문제 풀이 중첩 반복문을 이용한 풀이입니다. 반복문이 아닌 dfs 재귀로 풀 수 있는 방법도 있습니다. public Node connect(Node root) { Node node = root; while (node != null) { Node dummy = new Node(); Node needle = dummy; wh.. 2024. 1. 6. 230. Kth Smallest Element in a BST 문제 이진트리가 주어졌을때, k 번째로 작은 원소를 구하는 문제입니다. 예를들어 k=2 이면 아래의 이진트리 원소 중 2번째로 작은 원소는 2 입니다. (k=1 은 1이 됩니다.) 문제 풀이 이진트리는 왼쪽 자식 노드는 자신보다 작은 수, 오른쪽 자식 노드는 자신보다 큰 수가 할당되는 개념이 있습니다. 이러한 개념을 알고있으면, 중위순회(inorder) 를 하는 경우 1~4 까지 순차적으로 노드를 방문하게 됩니다. (참고. 중위순회는 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순서로 방문합니다.) 중위순회를 이용하여 문제를 푸는 방법으로 리스트에 원소를 저장하고 k 번째를 get 해서 리턴하거나, 리스트 없이 int index = 0 같은 변수를 할당하고 k 와 같으면 값을 저장하는 방법이 있습니다. .. 2024. 1. 5. 이전 1 2 3 4 5 다음
