개발 일기

1. 문제 - 이웃 노드가 담긴 리스트, 그래프의 전체 복사본을 반환 2. 의사코드 1. 복사본을 저장하기 위한 Hash private HashMap map = new HashMap(); 2. 현재 노드 복사본 생성 Node newNode = new Node(node.val, new ArrayList()); 3. map에 현재 노드와 복사본 저장 map.put(node, newNode); 4. 반복문으로 복사본에 채우기 3. 시도 class Solution { private HashMap map = new HashMap(); public Node cloneGraph(Node node) { // 현재 노드가 null이거나 복사본에 현재 노드가 없을 때 if (node == null) { return nul..

Trie 원하는 원소를 찾기 위해 자주 이용되는 방법으로는 BST(Binary Search Tree)가 있다. Trie는 트리의 일종으로 문자열의 키를 효율적으로 저장하고 빠르게 검색하기 위한 자료구조이다. 트라이의 중요한 속성 중 하나는, 루트에서부터 하위 경로까지 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다는 것이다. 1. 문제 - 주어진 단어를 Trie에 삽입, 검색, 접두사 시작 확인 메서드를 구현하라 2. 의사 코드 한 번에 세 개의 메서드를 구현해야 했다. 메서드를 구현하기 전에 입력받은 문자열의 매 문자들을 노드로 저장하기 위한 설계가 필요해 보인다. Trie 객체를 초기화하면 root 변수는 생성자를 통해 map, inEnd 속성을 갖는다. public class T..

1. 문제 - 이진 검색 트리에서 k번째로 작은 값을 구해라 2. 의사코드 이번 문제도 이전에 풀었던 leetcode 530번 문제와 비슷했다. 재귀를 이용해 노드를 정렬하고 k번째 노드의 값을 출력하면 될 것 같았다. 530번 문제의 내용은 링크에서 https://rhdqors.tistory.com/107 확인 가능하다. 1. 변수 설정 (재귀, 정렬된 값 저장) Integer data = null; ArrayList lists = new ArrayList(); // 우선 List를 이용해 정렬된 값을 저장시켜 본다 2. 재귀함수, 값 정렬 public void 재귀(TreeNode node) { 재귀(node.left); // 왼쪽 하위 트리 탐색 data = node.val; // 각 노드의 값 l..

1. 문제 - 주어진 노드에서 Binary Search Tree를 사용하여 최솟값을 찾아라 2. 의사코드 Binary Search Tree에서 많이 사용하는 방법에는 크게 BFS, DFS 두 가지가 있다. BFS(Breadth-First Search) - 너비 우선 탐색 트리의 레벨별로 노드를 탐색하며 일반적으로 큐를 사용하여 구현한다. DFS(Depth-First Search) - 깊이 우선 탐색 In-Order Traversal (중위 순회): 왼쪽 하위 트리를 먼저 탐색하고 -> 현재노드 -> 오른쪽 하위 트리 순서로 탐색하며 오름차순 정렬이다. Pre-Order Traversal (전위 순회): 현재 노드 -> 왼쪽 하위 트리 -> 오른쪽 하위 트리를 탐색한다. Post-Order Traversa..

1. 문제 - 양 옆의 요소들보다 큰 숫자 peak를 찾아라 2. 의사코드 peak란 nums[i]가 있다고 가정했을 때 nums[i-1]보다 크고 nums[i+1]보다도 커야한다. 1. 이진 탐색 인덱스를 설정한다 int left = 0; int right = nums.length-1; 2. nums의 중간값을 taget으로 정한다 while(left nums[mid+1]) { return mid; . . . }3. 시도 class Solution { public int findPeakElement(int[] nums) { int left = 0; int right = nums.length-1; // System.out.println(left + ", " + right); if(nums.length =..

1. 문제 - 배열의 요소를 더해 target이 되는 값을 찾고 해당 값들의 인덱스번호를 반환 2. 의사 코드 배열의 모든 값을 검사하는 완전 탐색을 제외하고 두 가지를 생각했던 것 같다. 요소들을 더해 target을 찾을 것인지, target에서 요소들을 빼면서 찾아갈 것인지. 아래는 target에서 요소들을 빼가는 코드이다. 1. target에서 배열의 요소들 - 하기 for(int i=0; 배열 길이만큼; i++) { int minus = target - 배열 요소; if 배열 요소가 map에 있다면 return [인덱스, map에서 찾은 값]; map.put(키, 벨류) }3. 시도 class Solution { public int[] twoSum(int[] nums, int target) { H..

1. 문제 *- 입력받은 String배열 tokens을 역폴란드 표기법(후위표기법)으로 정해진 수를 만들어라 * 2. 의사 코드 입력받은 배열 tokens의 연산자 or 피연산자를 확인하여 서로 다른 Stack에 넣고 연산자(+,-,*,/)가 나왔을 때 숫자가 담긴 Stack의 값을 꺼내어 연산을 하면 될 것 같았다. 1. tokens의 요소가 숫자인지 확인 boolean 타입의 메서드 생성 2. tokens의 요소가 연산자인지 확인 boolean 타입의 메서드 생성 3. 숫자가 담길 Stack과 연산자가 담길 Stack 구분 및 필요한 변수 선언 int sum = 0; // 결과 변수 String stringTokens = Arrays.toString(tokens); // 배열의 모든 요소 확인하기 위..

1. 문제 - 상수 시간 안에 push, pop, top, 최소 원소 검색을 제공하는 stack을 설계하라 Stack 이란? 후입선출(LIFO / Last-In-First-Out): 최근 추가된 요소가 먼저 제거되고 먼저 추가된 요소가 나중에 제거된다. 이해하기 쉬운 예시로 식당에 줄을 서있는데 늦게 온 사람이 먼저 들어가는 것 이라고 생각하면 된다. 즉 출입구가 하나인 박스에 요소를 쌓는 것이다. push : 스택에 data 넣음. pop : 스택 맨 위의 data 제거. -> 가장 마지막에 push 한 data가 가장 먼저 pop 된다. peek : pop과 유사하게 맨 위의 data 반환 -> 스택에서 제거되지 않음. top : 가장 마지막에 추가된 data의 위치 (가장 맨위) 2. 의사 코드 1..

먼저 이번 문제의경우 문제를 보고도 이해하지 못했고 접근 방식도 전혀 몰랐기에 코드에대한 분석 or 리뷰 정도가 될 것 같다. 1. 문제 - Linked List가 주어지면 목록에 순환이 포함되어 있는지 확인하는 문제 2. 정답 코드 // Definition for singly-linked list. // class ListNode { // int val; // ListNode next; // ListNode(int x) { // val = x; // next = null; // } // } public class Solution { public boolean hasCycle(ListNode head) { } } 문제를 들어오면 가장 윗부분에 주석된 코드가 있을 것이다. 아마도 Linked List의 흐..

1. 문제 - 중복되지 않은 연속된 문자의 가장 큰 길이를 구하여라 2. 의사 코드 비어있는 리스트를 생성하고 문자열 s를 char로 한 문자씩 빈 리스트에 중복 체크하여 넣고 리스트 길이를 출력하면 될 것 같았다. 1. 빈 리스트 생성 ArrayList lists = new ArrayList(); 2. 반복문으로 lists에 문자가 있는지 확인 후 추가 for (int i=0; i