kwang2134 님의 블로그

[Grind75-LeetCode] Word Ladder - Hard접근bfs풀이 시작 단어와 목표가 될 끝 단어가 존재하고 단어 리스트에 있는 단어들을 타고 끝 단어에 도착할 수 있는지 구하는 문제이다. 시작 단어를 단어 리스트에 있는 문자들로 변환할 수 있다면 변환하며 끝 문자를 만드는 데 걸리는 횟수를 구하는 것이 목표인데 변환이 가능한 기준은 각 단어가 문자 한 개만 다르다면 변환이 가능하다. 알파벳 단위로 시작 단어가 hot이고 리스트 내에 hit이라는 단어가 존재한다면 두 번째 문자인 o과 i만 다르고 나머지가 동일하기 때문에  변환이 가능하다.  이 문제는 옛날에 코딩 테스트를 준비하며 공부할 때 풀었던 문제이다. 프로그래머스의 단어 변환이라는 문제로 프로그래머스 기준 레벨 3의 문제였다. 프..

[Grind75-LeetCode] Find Median from Data Stream - Hard 접근heap (우선순위 큐)풀이중앙값을 찾는 클래스를 구현하는 문제이다. 중앙값이란 주어진 원소들을 순서대로 나열했을 때 중앙에 위치한 값을 말한다. 홀수인 경우 중앙값은 하나이지만 짝수인 경우 한 개의 중앙값이 존재하는 것이 아닌 중앙에 위치한 두 개의 값을 더하여 2로 나눈 값이 중앙값이 된다. 1,2,3,4 가 있다면 중앙의 2,3을 더한 값인 5에서 2로 나눈 2.5가 중앙값이 된다. 이러한 중앙값을 찾을 수 있는 클래스를 구현해야 하는데 정수를 추가하는 addNum과 중앙값을 반환하는 findMedian 두 메서드 구현이 목표이다. 이 문제는 간단하게 생각하면 배열을 두고 길이를 통해 중앙값 인덱스..

[Grind75-LeetCode] Trapping Rain Water - Hard접근투 포인터풀이양의 정수 값으로 배열이 주어지고 정수 값들은 벽(?)의 높이를 나타낸다. 그렇게 만들어진 벽에 비가 올 경우 물이 고이게 되는데 고인 물의 총량을 구하는 문제이다. 저번에 풀었던 컨테이너? 를 만드는 문제와 비슷하다.2024.11.19 - [알고리즘/코딩테스트-Grind75] - [Grind75-LeetCode] Container With Most Water JAVA [Grind75-LeetCode] Container With Most Water JAVA[Grind75-LeetCode] Container With Most Water - Medium 접근투 포인터풀이수직선의 길이가 들어있는 배열이 주어지고 수..

[Grind75-LeetCode] Serialize and Deserialize Binary Tree - Hard접근전위 순회풀이이진트리의 직렬화, 역직렬화를 구현하는 문제이다. 직렬화란 프로그램 내에서 복잡한 데이터 구조인 객체, 트리, 그래프 등을 바이트 스트림 또는 문자열 형태로 변환하여 파일에 저장하거나 네트워크를 통해 전송할 수 있게 하는 개념이다. 복잡한 데이터를 일관된 형식으로 표현하여 직렬화 한 뒤 데이터를 전송하고 받은 직렬화된 데이터를 역직렬화하여 데이터 구조를 복원하여 사용한다. 이번 문제는 이진트리의 직렬화 과정과 역직렬화 과정을 구하는 문제인데 주어진 코드는 문자열 직렬화이지만 채점 기준으로 각 직렬화, 역직렬화를 통해 동일한 값을 얻을 수 있느냐 즉 정상적으로 직렬화와 역직렬화가..

[Grind75-LeetCode] Minimum Window Substring - Hard접근슬라이딩 윈도우풀이LeetCode에서 푸는 첫 Hard 문제로 Grind75에서 easy와 medium 문제는 끝이 나고 hard 난이도 문제가 시작되었다. 이 문제는 문자열 s, t가 주어지는데 문자열 t가 s안에 포함되는 가장 작은 단위의 부분 문자열을 구하는 문제이다. 문자열 t에 존재하는 문자들이 모두 포함되기만 하면 된다.s = "ADOBECODEBANC", t = "ABC"예제 1번으로 t의 문자가 모두 포함된 가장 짧은 길이인 "BANC"가 정답이 된다. t의 문자인 A, B, C가 모두 포함되어 있기 때문이다.  문제에서 window라고 했듯이 슬라이딩 윈도우를 사용하면 O(n + m)을 만족하며 ..

[Grind75-LeetCode] Kth Smallest Element in a BST - Medium접근중위 순회풀이BST, 이진 탐색 트리에서 K번째로 작은 요소를 찾아 반환하는 문제이다. 이진 탐색 트리이기 때문에 루트를 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 나눠지기 때문에 그 점을 이용해 값을 찾으면 된다.  기본적으로 K번째 작은 값을 찾아야 하기 때문에 왼쪽 서브트리의 작은 값을 기준으로 탐색을 시작해야 한다. 루트를 기준으로 왼쪽 맨 아래 서브트리부터 탐색을 시작해 해당 서브트리의 루트, 오른쪽 서브트리 순으로 탐색을 진행해야 한다. 맨 아래 왼쪽 서브트리가 가장 작은 값이고 그다음으로 작은 값이 해당 노드의 루트 그리고 그다음으로 작은 값이 오른쪽 노드인데 이 순회의 형태는 중위 순..

[Grind75-LeetCode] LRU Cache - Medium접근Doubly Linked List 풀이 LRU (Least Recently Used) 가장 최근에 사용되지 않은 캐시를 교체하는 알고리즘으로 오늘 문제에서 구현해야 할 내용이다. 구현해야 할 부분은 LRU 클래스의 생성자, get, put 메서드로 생성자의 경우 LRU 캐시의 크기를 넘겨받게 된다. get은 말 그대로 캐시에 들어있는 값을 반환하는 메서드로 캐시에 존재하지 않을 경우 -1을 반환한다. put은 캐시에 값을 넣는 메서드로 값은 key, value 형태로 주어진다. 이러한 교체 알고리즘을 구현하는 문제는 이 전에도 존재했었는데 아무래도 문제의 거의 막바지에 다다른 만큼 평범한 방식으론 풀 순 없지 않을까 싶다.  우선 내용..

[Grind75-LeetCode] Task Scheduler - Medium 접근그리디풀이작업 스케줄러라는 문제로 주어지는 작업을 CPU가 처리하는데 몇 번의 인터벌이 필요한지 구하는 문제이다. 알파벳 대문자로 주어지는 작업이 들어있는 배열과 정수 n이 주어지는데 한 작업은 n의 시간이 지난 뒤에 다시 처리할 수 있는 규칙이 있다. n = 2라면 작업 A가 처리되고 2라는 시간이 흐른 뒤에 다시 처리가 가능해진다는 뜻이다. 1번째에 A가 처리되었다면 2 턴이 지나고 4번째부터 다시 처리가 가능하다.  문제의 설명에서와 예제에서 작업이 배열로 주어지지만 배열 순서에 상관없이 작업 처리가 가능하다고 나와있었다. 그렇다면 처리해야 할 횟수가 많은 작업을 적재적소에 배치하는 것이 중요한데 n이라는 쿨다운 시간이..

[Grind75-LeetCode] Minimum Height Trees - Medium접근리프 노드 제거풀이트리는 두 정점이 하나의 경로로 연결된 무방향 그래프로 사이클이 존재하지 않는 무방향 그래프는 트리라고 부를 수 있다. 트리는 루트에 따라 트리를 구성하는 높이가 달라지는데 이번 문제는 무방향 그래프에서 트리의 높이를 가장 낮게 구성할 수 있는 루트 노드들을 찾아 반환하는 문제이다. 무방향 그래프를 트리로 봤을 때 높이가 3이 최소가 된다면 3의 높이로 트리를 구성할 수 있는 루트 노드를 모두 찾는 것이다. 문제가 점점 어려워지고 있는 것 같다. 구할 수 있는 방법은 여러 가지가 있을 것이다. 각 정점 간의 거리를 구해 가장 멀리 있는 두 정점을 구하고 두 정점 가운데 정점을 루트로 사용하면 최소 ..

[Grind75-LeetCode] Find All Anagrams in a String - Medium접근슬라이딩 윈도우풀이문자열 s 내에서 애너그램 부분 문자열 p가 존재하는지 찾는 문제이다. p 문자열을 애너그램으로 만들 수 있는 s의 시작 인덱스를 모두 찾아 리스트에 담아 반환하면 된다. 단순하게 맵에 p의 문자 등장수를 담아둔 뒤 각 자리마다 반복을 통해 계산해 보니 당연하게도 시간초과가 나왔다. 그러니 이 문제는 s의 길이가 m, p의 길이가 n이라면 적어도 O(m * n)의 복잡도 보다 빠른 방법으로 해결되어야 한다.  슬라이딩 윈도우 기법을 사용하면 s를 한 번의 순회로 해결이 가능하기 때문에 O(n)의 시간 복잡도로 해결이 가능하다. public List findAnagrams(Str..