👨🏻‍💻 PS/LeetCode 150

[Java] 909. Snakes and Ladders

문제 파악 Boustrophedon 스타일의 n*n 보드가 주어진다. ( (n-1,0) 좌표에서 시작한다. ) 주사위에 따라 최대 6칸을 이동할 수 있다. 만약 뱀이나 사다리를 만나면 뱀이나 사다리를 이용해야한다. n^2 칸에 도달했을 때, 게임은 끝난다. 보드 값이 -1이 아닌 경우 뱀이나 사다리가 존재한다. 뱀이나 사다리인 경우 도착하는 보드 값이 기록되어있다. 뱀이나 사다리는 1 또는 n^2 칸에 존재하지 않고 연속으로 이동할 수 없다. n^2에 도달하기 위한 최소 이동 횟수를 반환하고, 도달하지 못하면 -1을 반환한다. 풀이 1️⃣ 1차원 맵과 bfs 를 이용한 방법 💡 떠오른 Idea 먼저, 보드판 순서가 헷갈려서 이를 1차원 맵으로 바꿔서 해결하면 간단할것이라 생각이 들었다. 따라서, 제일 아..

[Java] 133. Clone Graph

문제 파악 노드로 연결된 그래프가 주어지고, 해당 그래프를 깊은 복사해서 반환해야한다. 풀이 1️⃣ bfs 를 이용한 풀이 💡 떠오른 Idea 깊은 복사를 하기 위해서는 어쩃든, 모든 노드에 방문해보고 해당 값을 갖는 새로운 노드를 생성해야한다. 문제에서 val 값은 unique 하다고 했으므로 map에 val 을 키값으로 해서 노드를 참조해준다. 첫번째 노드부터 이웃 노드들에 방문해보고, map에 들어있지 않은(아직 방문하지 않은) 노드들은 큐에 집어넣어 이웃 노드들에 방문하기를 반복한다. 만약 map에 들어있는(방문했던) 노드라면 큐에 넣지 않고 이웃으로서 추가만 해준다. class Solution { Map map = new HashMap(); Queue q = new LinkedList(); pu..

[Java] 373. Find K Pairs with Smallest Sums

문제 파악 비 내림차순인 두 정수 배열 nums1 과 nums2 그리고 k가 주어진다. k개의 가장 합이 작은 pair 를 반환해야한다. 풀이 1️⃣ PriortyQueue 와 일종의 그리디 법을 활용 💡 참고한 Idea 이번 문제는, 아무리 열심히 떠올려봐도 시간 초과 & 메모리 초과 때문에 해결하지 못하고 다른 사람의 아이디어를 참고하여 해결하였다. 핵심 아이디어는 다음과 같다. 먼저, 두 원소의 합을 기준으로 오름차순으로 정렬하는 우선순위 큐를 준비한다. nums1 배열의 인덱스는 0 으로 고정한 채, nums2 배열을 순회하며 합을 구하고 우선순위 큐에 입력한다. 우선순위 큐에는 [ nums1의 값, nums2 의 값, nums1의 인덱스, nums1의 값 +nums2의 값 ] 으로 입력해준다. ..

[Java] 215. Kth Largest Element in an Array

문제 파악 정수 배열 nums 가 주어지고 k가 주어진다. k번째로 큰 원소를 반환하면 된다. 풀이 1️⃣ PriorityQueue를 활용한 풀이 💡 떠오른 Idea 내림차순으로 정렬하는 우선순위큐에 원소들을 넣고 k번째의 원소를 반환한다. import java.util.*; class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue pq = new PriorityQueue((a, b) -> b - a); for (int num : nums) { pq.offer(num); } int ans = 0; while (k-- > 0) { ans = pq.poll(); } return ans; } } 결과 📖 회고 너무 간단하게 문제..

[Java] 212. Word Search II

문제 파악 문자가 채워져있는 m*n 크기의 보드가 주어진다. 문자열이 주어지는데, 해당 문자열을 만들 수 있으면 반환한다. 풀이 1️⃣ 백트래킹과 Set 이용한 풀이 💡 떠오른 Idea 백트래킹으로 만들 수 있는 문자열을 모두 구해본다. ( 최대 길이 10으로) 구한 문자열을 Set 에 넣고, 주어지는 문자열이 Set에 들어있는지 확인한다. import java.util.*; class Solution { int R; int C; boolean[][] checked; StringBuilder str = new StringBuilder(); int[] dr = {1, -1, 0, 0}; int[] dc = {0, 0, 1, -1}; char[][] board; Set set = new HashSet(); ..

[Java] 211. Design Add and Search Words Data Structure

문제 파악 특정 문자열을 보관하고 search 했을 때, 존재하면 true를 반환하는 자료구조를 만들어야한다. . 이 포함된 경우는 어떠한 문자가 들어가도 허용된다. 풀이 1️⃣ Trie 자료구조를 이용한 풀이 💡 떠오른 Idea Trie 자료구조를 이용하면 접두어나 부분 문자열을 검색할 수 있다. 따라서, Trie 자료구조를 구현하였다. 특히, 이 문제에서는 search 과정에서 . 이 포함되어 있는 경우는 해당 노드가 갖는 모든 자식 노드들을 탐색하도록 구현하여 해결할 수 있을 것이라 판단하였다. import java.util.*; class WordDictionary { static class Node { Map children; boolean isEndOfWord; public Node() { t..

[Java] 208. Implement Trie (Prefix Tree)

문제 파악 Trie 자료구조를 구현해야하는 문제이다. 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 해시 테이블을 사용하면 되는데, 왜 트라이를 사용해야할까? 🚨 해시 테이블의 경우 접두사나 부분 문자열로 검색하기 힘들다. 또한, 해시 코드로 저장하기 때문에 정렬되어 있지 않다. 풀이 1️⃣ Node 클래스 정의 class Trie { Node root; static class Node { Map children; boolean isEndOfWord; public Node() { this.children = new HashMap(); this.isEndOfWord = false; } } public Trie() { this.root = new Node(); } } Trie..

[Java] 637. Average of Levels in Binary Tree

문제 파악 각 level(depth)의 노드들의 val 값 평균을 구해서 반환해야한다. 풀이 1️⃣ 그래프 탐색을 이용한 풀이 (전위 탐색) 💡 떠오른 Idea 전위 탐색을 depth를 1씩 증가시키면서 탐색을 한다. 각 depth에 도달했을 때, 해당 depth의 합과 개수를 저장하는 List를 통해 정보를 갱신한다. 탐색이 끝나고 나서, 평균 값을 구해서 반환해준다. import java.util.*; class Solution { List list = new ArrayList(); public List averageOfLevels(TreeNode root) { List ans = new ArrayList(); preOrder(root, 0); for (int i = 0; i < list.size()..

[Java] 199. Binary Tree Right Side View

문제 파악 주어지는 트리를, 오른쪽에서 바라보았을 때 보이는 노드들을 반환해야한다. 문제 해석 시, 약간 혼동이 있어서 처음에는 트리의 가장 오른쪽 노드들을 출력해야하는 줄 알았다. 따라서 위와 같이 구성된 트리의 경우, root 노드의 right node 는 없기 때문에 결과가 [1] 이 나와야 된다고 생각했는데 요구하는 답은 [1,2] 였다. 해석을 찾아보니, 이 트리를 오른쪽에서 바라봤을 때 보이는 노드들을 출력하라는 뜻이었다. 풀이 1️⃣ 전위 탐색을 이용한 풀이 💡 떠오른 Idea 전위 탐색의 경우 위와 같이 루트 노드에서 시작하여 왼쪽 혹은 오른쪽 경로의 끝에 도달하면 부모의 반대편 노드로 넘어가는 방식으로 탐색한다. 위 문제의 경우는 가장 오른쪽을 탐색해야하므로 경로를 오른쪽으로 시작하도록 ..

[Java] 230. Kth Smallest Element in a BST

문제 파악 k번째로 작은 값을 출력해야한다. 풀이 1️⃣ 중위 순회를 이용한 풀이 💡 떠오른 Idea 트리 구조에서 중위 순회를 하면 오름차순 순서로 노드 데이터를 출력할 수 있다. 이러한 원리를 적용하여 k번째 노드에 접근했을 때, 값을 저장하도록 구현하면 되겠다고 판단하였다. class Solution { int ans = 0; int idx = 1; public int kthSmallest(TreeNode root, int k) { inOrder(root, k); return ans; } private void inOrder(TreeNode node, int k) { if (node == null) { return; } inOrder(node.left, k); if (idx == k) { ans =..

[Java] 530. Minimum Absolute Difference in BST

문제 파악 트리 안에 존재하는 임의의 두 노드의 차 중 최솟값을 반환해야한다. 풀이 1️⃣ 중위 순회를 이용한 풀이 💡 떠오른 Idea 노드 구조에서 중위 순회를 하면서 노드 값을 출력하면 오름차순으로 정렬된 데이터를 얻을 수 있다는 특징을 이용하였다. 첫번째 노드는 이전 노드가 존재하지 않으므로, 계산을 생략한다. 그리고 이전 노드 값에 기록해준다. 두번째 노드에 도달했을 때, 이전 노드 값과의 차이를 구하고 갱신한다. 갱신 후, 이전 노드 값에 두번째 값을 기록해준다. .... 위 과정을 반복하는 방식이다. class Solution { int ans = Integer.MAX_VALUE; Integer prev = null; public int getMinimumDifference(TreeNode r..

[Java] 153. Find Minimum in Rotated Sorted Array

문제 파악 rotated 된 배열 nums의 최솟값을 찾는 문제이다. 시간 복잡도는 O(logN) 을 만족해야한다. 풀이 1️⃣ 이분 탐색을 이용한 풀이 💡 떠오른 Idea 이전에 풀었던 Search in Rotated Sorted Array 문제의 일부분과 같은 문제라서 쉽게 해결할 수 있었다. 이분 탐색을 진행하는데, mid 위치의 값과 right 위치의 값을 비교해서 mid 값이 작은 경우, mid 위치의 원소들은 오름차순으로 구성되어 있음을 보장할 수 있기 때문에 탐색 영역을 왼쪽 영역으로 이동하는 방식으로 구현하면 된다. class Solution { public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (le..

[Java] 33. Search in Rotated Sorted Array

문제 파악 오름차순으로 정렬되어 있는 배열 nums가 있었다. 인덱스 k번째 원소가 제일 첫 원소가 되도록 rotated 되어있다. target 이 배열 nums 에 포함되어있는지 O(logN) 으로 탐색하여 인덱스를 반환해야한다. 풀이 1️⃣ 이분 탐색을 이용한 풀이 💡 떠오른 Idea 먼저, 주어진 시간 복잡도를 만족하기 위해선 이분 탐색을 사용해야함을 알 수 있었다. 결과적으로는, target이 nums에 존재하는지를 이분 탐색해야하는데 특정 값을 탐색하기 위해선 정렬되어있어야 한다. 따라서, rotated된 배열을 정렬된 두개의 배열로 나누기 위해 배열 내의 최솟값을 검색한다. ex) [4, 5, 6, 7, 0, 1, 2] 배열이 있을 때, [4, 5, 6, 7] 과 [0, 1, 2] 배열 2개로..

[Java] 162. Find Peak Element

문제 파악 주변 원소들보다 큰 원소를 peak element라고 한다. 그러한 원소가 여러개라면 아무 원소의 인덱스를 반환하면 된다. 시간 복잡도가 O(logN) 이 되도록 구현해야한다. 풀이 1️⃣ 이분 탐색을 이용한 풀이 💡 떠오른 Idea 시간복잡도를 통해 이분 탐색을 이용해야함을 알 수 있었다. 보통 이분탐색은 정렬된 배열에서만 사용해와서, 이분 탐색을 어떻게 활용할 수 있을지 오랫동안 생각해보았다. mid 포인트 값이 mid + 1 포인트 값보다 작다면? mid 포인트 값은 peak element 가 될 확률이 존재하지 않는다. 따라서 탐색 범위를 mid+1 이상으로 잡아줘야 할 것이다. 만약, mid 포인트 값이 mid + 1 포인트 값 보다 크다면 mid 포인트 값은 peak element ..

[Java] 148. Sort List

문제 파악 연결 리스트의 head가 주어진다. 오름차순으로 정렬해서 반환해야한다. 풀이 1️⃣ 배열과 mergeSort 💡 떠오른 Idea O(NlogN) 방식으로 해결하기 위한 방법을 떠올려봤다. 해당 시간 복잡도로 정렬할 수 있는 Merge Sort 방식을 사용해야 해결할 수 있을 것이라 판단했다. class Solution { public ListNode sortList(ListNode head) { int cnt = getCount(head); System.out.println(cnt); int[] arr = new int[cnt]; ListNode dummyHead = new ListNode(0, head); ListNode node = head; for (int i = 0; i < cnt; i..