분류 전체보기

[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] 백준 1781번 【G2.컵라면】

문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 1️⃣ 우선 순위 큐와 그리디를 이용한 풀이 💡 떠오른 Idea 컵라면을 데드라인이 짧고 컵라면을 많이 주는 문제부터 결정해서 큐에 집어넣는다. 즉, 큐의 크기 = 풀기로 결정한 문제 수 = 내가 문제를 푸는데 사용한 시간이 된다. 그리고, 이후에 나오는 문제들이 내 큐의 크기보다 크거나 같으면서 내 큐에 들어있는 컵라면보다 많이 준다면 내 큐에 들어있던 가장 컵라면을 적게 주는 문제를 제거하고, 추가해준다. 예제로 원리를 설명해보면, 먼저, 데드라인이 짧은 ..

[JAVA] 백준 1655번 【G2.가운데를 말해요】

문제 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 1️⃣ 우선 순위 큐 두개를 활용한 풀이 💡 떠오른 Idea 우선 순위 큐는 이진 힙 방식으로 구성되어 있기 때문에, 사용하면 정렬을 유지한 삽입 과정을 O(logN) 에 수행할 수 있다. 그리고, 우선 순위 큐에 따라 정렬된 데이터를 꺼낼 때 역시, O(logN) 로 수행할 수 있다. 따라서 우선 순위 큐를 사용하는게 시간 복잡도를 만족시킬 수 있다고 판단하였다. 가운데 수를 항상 말해야 하므로, 내림차순으로 정렬된 우선순위 큐 (l..

[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] 백준 1715번 【G4.카드 정렬하기】

문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 1️⃣ PriorityQueue 를 활용한 풀이 💡 떠오른 Idea 약간, 그리디 처럼 생각을 해보았다. 누적으로 묶음의 수만큼 합쳐지므로, 가장 작은 묶음의 수만 중복으로 값에 더해져야한다. 결론은, 카드 묶음을 합치는데 남은 카드 묶음 중에서 가장 작은 두 묶음을 골라서 합쳐야 한다. 카드 묶음을 합치게 되면, 다른 후보 묶음들 보다 커지게 될 수도 있고 여전히 작을 수도 있다. 따라서, 일단은 이 카드 묶음을 다시 후보로 올려두고,..

[JAVA] 백준 23326번 【G3.홍익 투어리스트】

문제 23326번: 홍익 투어리스트 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, www.acmicpc.net 풀이 1️⃣ treeSet을 이용한 풀이 💡 떠오른 Idea 구역의 개수가 500000 이고 쿼리의 개수가 100000 이므로 선형탐색을 하게되면 시간복잡도가 최대 500000*100000 으로 절대 통과 못하는 수치가 나온다. 따라서, treeSet을 이용한 풀이가 필요하다. treeSet의 대부분의 메서드는 log(N) 의 성능으로 동작하기 때문이다. treeSet에 명소 번호를 갱신하고, 쿼리문을 수행하면서 도현이의 위치도 갱신한다...

Hash 자료구조와 해시 충돌

Hash Table 이란 Hash Table은 데이터를 key-value 형식으로 보관하여 검색 · 삽입 · 삭제를 O(1) 시간 복잡도로 수행할 수 있는 자료구조이다. Hash Table은 key 값을 통해 데이터를 다루기 때문에, key 값은 고유해야한다. 이러한 고유한 key 값을 만드는 작업은 해시 함수가 담당하는데, 대표적으로는 key 값의 ASCII 값을 합하여 만드는 간단한 방법이 있다. 이러한 해시 함수가 key를 만드는 과정에서, 의도하지 않게 우연히 key 값이 일치하는 경우가 발생할 수 있는데 💡 이를 해시 충돌이라고 한다. 해시 충돌이 발생하면, key 값이 중복되어 데이터가 사라질 수 있다. 따라서 해시 충돌이 발생하면 대처해야한다. 대표적인 방법으로는 체인법 (Seperate C..