ETC/Algorithm
-
[LeetCode/JAVA] 133. Clone GraphETC/Algorithm 2023. 9. 15. 14:57
문제 주어진 그래프를 복사를 하는 문제이다. 풀이 DFS를 통해 전체를 복사하여 HashMap에 저장하고 복사하여 풀이하였다. 코드 class Solution { private HashMap visited = new HashMap (); public Node cloneGraph(Node node) { if (node == null) return null; if (visited.containsKey(node)) return visited.get(node); Node cloneNode = new Node(node.val, new ArrayList()); visited.put(node, cloneNode); for (Node neighbor: node.neighbors) { cloneNode.neighbors..
-
[LeetCode/JAVA] 208. Implement Trie (Prefix Tree)ETC/Algorithm 2023. 9. 12. 01:35
문제 trie라는 트리 데이터 구조를 구현하는 문제이다. Trie() 는 trie 객체의 시작을 구현해야하고, insert()는 word라는 문자열을 trie 트리에 입력을 구현, search()는 문자열 word가 trie에 존재하는지를 구현하고, startsWith()는 접두사 문자열 prefix가 주어질 때 접두사가 일치하는 단어가 존재하는지를 구현해야한다. 풀이 일단 해당 문제는 소문자로만 이루어진 문자열을 활용해서 String을 char로 변환해서 트리 노드에 하나씩 저장하는 방식을 먼저 구현해야했다. 그리고 노드를 타고 하위 노드로 내려갔을 때, 해당하는 단어가 단순한 문자열의 나열인지 실제 단어인지를 판단 할 수 있어야 했다. 왜냐하면 예시를 보면 apple이라는 단어가 insert 되어있고..
-
[LeetCode/JAVA] 230. Kth Smallest Element in a BSTETC/Algorithm 2023. 9. 7. 19:37
문제 이진 탐색 트리가 주어질 때, 정수 K가 주어지고 이진 탐색 트리에서 K번째로 작은 노드의 값을 출력하는 문제이다. 풀이 이전 최소 차이값을 찾는 문제와 동일하다. 중위 탐색을 사용하면 오름차순으로 조회가 가능하기 때문에, 제일 왼쪽 루트부터 시작해서 count를 증가시키면서 주어진 k와 같을 때 result에 값을 저장하고 반환하면 되는 문제다. 코드 public class Solution { int count = 0; int result = 0; public int kthSmallest(TreeNode root, int k) { inorder(root, k); return result; } private void inorder(TreeNode root, int k) { if (root == nu..
-
[LeetCode/JAVA] 530. Minimum Absolute Difference in BSTETC/Algorithm 2023. 9. 7. 19:17
문제 이진 탐색 트리(BST)가 주어질 때, 트리의 두 노드간 가장 작은 차이를 찾고 그 값의 절대값을 반환하는 문제이다. 풀이 가장 먼저 이진 탐색 트리라는 형태를 생각했을 때, 노드 구조가 왼쪽은 작은 값 오른쪽은 큰 값 중간은 왼쪽과 오른쪽 값의 중간이다. 가장 작은 값을 찾기 위해서는 트리의 전체를 순환해야 찾을 수 있다고 판단하고, 어떻게 돌아야 차이를 찾을 수 있을까 고민했을 때 중위 탐색을 하면 왼쪽 -> 중간 -> 오른쪽 순으로 탐색하는 점을 생각했다. 이렇게 될 경우 예시 1의 경우 시작을 1로하여 순서대로 1-2-3-4-6 순으로 진행하게 될 것이므로 오름차순으로 조회가 가능하다. 코드 public class Solution { Integer prev = null; Integer min..
-
[LeetCode/JAVA] 162. Find Peak ElementETC/Algorithm 2023. 9. 3. 15:33
문제 주변 보다 큰 요소를 peak 요소라 부르는데, 이 peak이라는 요소의 아무 인덱스나 반환하는 문제이다. 여기서 O(log n)을 만족하는 알고리즘을 사용해야한다. 풀이 배열의 요소의 주변은 왼쪽 오른쪽으로 생각할 수 있다. 이 둘 보다 클 때 peak이라는 요소가 되므로 이에 알맞는 알고리즘을 선택해야했고, 이분 탐색(bineary search) 알고리즘을 사용해서 풀이할 것이다. 시작은 배열의 시작 0과 끝 nums.length - 1 에서 부터 시작할 것이다. 배열의 중간을 구하기 위해 ( 왼쪽 인덱스 + 오른쪽 인덱스 ) / 2 를 계산하여 중간 인덱스 값을 구하고, 이 중간 인덱스의 위치한 nums의 요소를 오른쪽 요소와 비교한다. 만약 중간 값이 작다는 것은 오른쪽 값이 더 크므로, 왼..
-
[LeetCode/JAVA] 1. Two SumETC/Algorithm 2023. 8. 31. 22:51
문제 배열 nums가 주어지는데 이 요소들을 중복하지 않고 한 번만 사용해서 target이라는 값을 만드는 문제이다. 풀이 해쉬맵을 사용해서 target의 값과 nums[i]의 값의 차이를 조회해서 만약 존재한다면 그 값이 정답이다. 하지만 해쉬맵이 초기에는 비어있으므로 존재하지 않다면 put을 통해 해쉬맵에 내용을 저장해주면서 반복하다보면 O(N)만에 정답을 구할 수 있게 된다. 코드 class Solution { public int[] twoSum(int[] nums, int target) { HashMap hmap = new HashMap(); for (int i = 0; i < nums.length; i++) { if (hmap.containsKey(target - nums[i])){ return..
-
[LeetCode/JAVA] 155. Min StackETC/Algorithm 2023. 8. 31. 22:24
문제 Stack 자료구조의 push, pop, top을 디자인하고, 최소 요소를 조회를 할 수 있게 하는 문제이다. 풀이 기본적으로 JAVA에서 주어지는 자료구조를 사용하여 풀이를 진행하려했다. 하지만 최소값이 문제였다. getMin()을 사용하면 최솟값을 반환하는데, pop() 메소드는 가장 위에 있는 요소를 꺼내버리기 때문에 만약 pop() 한 대상이 최솟값이라면 getMin() 메소드를 할 때 반환할 최솟값을 다시 설정해줘야했다. push를 할 때 최소값을 판단하고 만약 최소값이라면 2번 푸쉬해준다. 아니라면 1번 푸쉬해준다. 이후 pop()을 진행할 때 최솟값과 비교한 뒤, 만약 최소값이라면 한번 더 pop() 메소드를 사용해서 최솟값을 변경해주는 과정을 진행해서 해결하였다. 코드 class Mi..
-
[LeetCode/JAVA] 125. Valid PalindromeETC/Algorithm 2023. 8. 27. 23:47
문제 모든 대문자 문자열을 소문자로 변경하고 영문, 숫자가 아닌 문자는 모두 제거한 문자열이 펠린드롬 문자열이라면 참을 반환하고 아니라면 거짓을 반환하는 문제이다. palindrome 펠린드롬이란? 앞 뒤를 뒤집어서 읽어도 똑같은 문장을 말한다. 풀이 일단 문자열에 필요없는 특수문자, 띄어쓰기 등을 없애야 원하는 문자열을 만들 수 있다고 판단해서 정규식을 사용해 문자열을 변환해준 다음, 소문자만 비교해야하기 때문에 toLowerCase() 메소드를 사용해서 전체 문자열에 대문자를 없애줬다. 펠린드롬의 경우 문자열을 뒤집어서 비교를 진행하고 서로 다른지 비교를 해야했는데, String 클래스의 길이를 사용하여 구현할 까 생각했지만 StringBuilder 클래스를 사용하면 reverse() 메소드로 간단하..