문제 요약 주어진 nums의 모든 subarray들의 (최대값 - 최소값) 들의 합을 구하는 문제였습니다. 이전의 풀어본 leetcode 907가 subarray의 최소값의 합이였기 때문에 이 문제를 기억하여 대략적으로 방향이 나올 수 있었습니다. 2023.05.01 - [Algorithm/problem solving] - leetcode 907. Sum of Subarray Minimums leetcode 907. Sum of Subarray Minimums 문제 요약 주어진 arr로 구성된 모든 subarray에서의 최소값들의 합을 구하는 문제였습니다. 해결 time limit exceed 접근법 처음에는 stack을 만들고 monotonic increasing stack을 만들고 매 index마다 ..
문제 요약 주어진 arr로 구성된 모든 subarray에서의 최소값들의 합을 구하는 문제였습니다. 해결 time limit exceed 접근법 처음에는 stack을 만들고 monotonic increasing stack을 만들고 매 index마다 stack에 들어있는 것을 꺼내어 답을 도출했습니다. 하지만 매 index마다 stack에 들어있는 것을 꺼내는 과정이 사실 이 문제는 O(n)으로 끝내야 하는 문제인데 최악의 경우 O(n^2) 케이스가 발생될 수도 있어 time limit exceed가 발생되고 말았습니다. 수학적 접근법 따라서 이를 해결하기 위해선 수학적 접근법을 이용할 수 있는데요. 우선 특정 범위 내에서 최소값이 정해진다고 할 때 그 수 주변에 왼쪽, 오른쪽을 고려해볼 수 있습니다. 만약..
문제 요약 minK, maxK를 만족하는 subarray가 몇 개가 있는지를 구하는 문제였습니다. 해결 문제는 간단했지만 subarray를 어떻게 나눌 것인지가 쉽지 않았습니다. O(n)으로 해결해야 하는 이런 문제의 경우 대부분의 케이스에 subarray를 나누는 것이 아닌 다른 접근법을 생각해야하는데 사실 그게 쉽게 떠오르지 않았고 결국 다른 사람의 답안을 참고하였습니다. 문제에서 포인터를 2개를 두어 해결하였습니다. minPos, maxPos라는 각각의 포인터는 문제의 요구사항을 충족하는 subarray의 index를 들고 있었고 그런 케이스가 없는 경우 -1이 갱신되지 않아 제대로 반영되지 않습니다. 2개의 포인터 외에 leftBound 변수가 있는데 이 값은 유효한 subarray의 개수를 셀 ..
문제 요약 여러개의 포인트(시작점, 끝점)들이 주어지고 화살을 쏠 때, 여러 포인트들을 모두 맞추는 최소의 화살 개수를 구하는 문제였습니다. 이 문제는 부분에 대한 최적의 해를 구하다보면 전체의 최적의 해에도 도달하는 Greedy Algorithm 문제였습니다. Greedy Algorithm (탐욕 알고리즘) 탐욕 알고리즘이란 그 당시(부분)의 최적의 해를 쫓아 최종적인 해답에 도달하는 방법을 말합니다. 이렇게 해결할 수 있는 문제는 2가지 특징이 있습니다. - 부분의 최적의 해를 쫒아 선택한 것은 그 다음 선택에 영향을 주지 않는다 - 최종적인 해답은 부분의 대한 최적의 해답들로 이루어진다 사실 Greedy Algorithm은 문제 풀 당시에는 '그냥 이렇게 하면 되지 않을까?'(이게 이 당시 최적 아..
문제 요약 입력값으로 (미팅 시작, 끝)이 주어지고 미팅을 잡을 때 사용할 수 있는 최소한의 회의실 개수를 구하는 문제였습니다. 해결 이 문제의 핵심은 회의 시작 순서로 정렬 후 회의실을 새로 잡을지, 아니면 기존 확보한 회의실을 사용할 수 있는지였습니다. 그것에 대한 판단은 PriorityQueue를 사용하여 찾아낼 수 있었습니다. 만약 (0, 30), (5, 10), (15, 20)이 주어져있다고 생각해봅니다. 만약 queue에 넣은 값 중 최소값이 현재 미팅의 시작 시간보다 크다면 새로운 회의실을 잡아야겠죠. 그렇지 않다면 기존 회의실을 쓰고 새로운 미팅의 끝 시작을 다시 queue에 넣어주면 됩니다(물론 기존 끝시간은 queue에서 빼구요) 교훈 우선 이런 문제는 기준점이 먼저 필요합니다. 그렇기..
문제 요약 입력값으로 get, add의 명령어와 더불어서 name, score의 리스트가 주어집니다. add 명령에 따라 name, score의 리스트를 순차적으로 넣되 get하는 시점에는 add한 것들 중 아래의 규칙대로 뽑아 반환합니다. score는 큰 순으로, 만약 같다면 name이 사전 정렬식으로 뽑는다 n번째 get을 할 때 뽑는 것도 앞에서부터 n번째 것을 뽑는다 해결 이 문제를 해결할 때 중점둬야 하는 것이 2가지 있습니다. 하나는 정렬이 필요하다는 것이고, 또 하나는 뽑을 때는 n번째로 뽑는 것을 가능한 빠르게 뽑아야 한다는 것입니다. 정렬을 하는 것은 흔하게 하는 것이다보니 크게 고민할 필요가 없으나, 그에 더불어서 n번째의 것을 뽑는 것은 좀 고민해봐야 하는 포인트였습니다. 여기서 기발..
