kwang2134 님의 블로그

[Grind75-LeetCode] Largest Rectangle in Histogram - Hard접근스택풀이Grind75의 마지막 문제로 히스토그램에서 가장 큰 사각형의 넓이를 구하는 문제이다. 이렇게 넓이를 구하는 유사한 문제에선 거의 슬라이딩 윈도우나 투 포인터를 사용했었지만 이번 문제는 끝 포인터들의 길이만 체크하는 것이 아니기 때문에 사용하기 어려운 방법이다.  어떻게 보면 더 간단한 방법일 수 있는데 스택을 사용해 푸는 것이다. 스택에 배열을 순회하며 값을 넣는다. 이전 스택에 들어있는 peek 값과 다음 진행에서 현재 인덱스의 값을 비교해 peek 값 보다 현재 인덱스 값이 크다면 스택에 값을 추가한 뒤 넘어가고 현재 인덱스 값이 작다면 스택에서 값을 꺼내 계산해 주면 된다. 쉽게 말해 스..

[Grind75-LeetCode] Merge k Sorted Lists - Hard 접근우선순위 큐분할 정복버킷 정렬풀이ListNode 객체를 정렬된 상태로 병합하는 문제이다. ListNode 객체는 필드로 값과 다음 ListNode의 참조 값을 가지고 있다. 이 문제를 봤을 때 주어진 노드의 순서를 알 맞게 배열해 하나의 ListNode로 만들어라는 말이겠지만 과연 채점 기준으로 객체의 참조값을 비교해 볼까?라는 생각이 들었다. 만약 참조 값을 기준으로 채점하지 않는다면 그냥 값들을 순서에 맞게 새로운 객체를 만든 뒤 반환하면 되기 때문이다. 코드가 복잡하지 않으니 한 번 해봤다. public ListNode mergeKLists(ListNode[] lists) { PriorityQu..

[Grind75-LeetCode] Maximum Profit in Job Scheduling - Hard접근dp이진 탐색풀이Job 스케줄러를 통해 얻을 수 있는 최대 이득을 구하는 문제이다. 시작 시간이 들어있는 배열, 종료 시간이 들어있는 배열 그리고 이익 값이 들어있는 배열이 주어진다. Job은 비선점 방식으로 수행이 되며 어떤 작업이 끝나는 시간에 다른 작업을 시작할 수 있다. 각 작업의 시간과 이득을 객체로 합쳐 놓고 종료시간을 기준으로 정렬한 뒤 dp와 이진 탐색을 통해 풀면 된다. 풀었던 방법과 성능이 제일 좋았던 코드는 알고리즘 자체는 동일하고 리스트를 사용하냐 배열을 사용하냐 정도의 차이였기 때문에 성능이 제일 좋았던 배열을 사용한 코드를 바로 들고 왔다. class Job { ..

[Grind75-LeetCode] Basic Calculator - Hard 접근스택풀이기본적인 계산기를 구현하는 문제로 문자열로 입력받은 수식을 계산한 결과를 반환하면 되는 문제이다. 수식에는 괄호가 포함될 수 있고 - 연산자는 단항 연산자로 사용이 될 수 있다. 즉 +의 경우 +1과 같이 앞에 다른 값 없이 단항 연산자로 사용될 수 없지만 -의 경우 -1과 같이 단항 연산자로 수식에서 사용될 수 있다.  무엇보다 이 문제에서 연산자는 +, - 두 가지만 존재한다. 곱하기 나누기 연산이 존재하지 않다 보니 괄호에 대한 처리만 스택을 통해 천천히 해주면 어렵지 않게 해결이 가능하다. public int calculate(String s) { Stack stack = new Stack()..

[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번째 작은 값을 찾아야 하기 때문에 왼쪽 서브트리의 작은 값을 기준으로 탐색을 시작해야 한다. 루트를 기준으로 왼쪽 맨 아래 서브트리부터 탐색을 시작해 해당 서브트리의 루트, 오른쪽 서브트리 순으로 탐색을 진행해야 한다. 맨 아래 왼쪽 서브트리가 가장 작은 값이고 그다음으로 작은 값이 해당 노드의 루트 그리고 그다음으로 작은 값이 오른쪽 노드인데 이 순회의 형태는 중위 순..