본문 바로가기

Medium174

[Leetcode][981] Time Based Key-Value Store 문제 : https://leetcode.com/problems/time-based-key-value-store/ timestamp를 key, value를 value로 하는 map을 하나만들고 이를 value 값으로 가지고 key값을 key로 가지는 unordered_map(정렬될 필요 없으므로)을 만든다.unordered_map m; // {key, {timestamp, value}}cs즉, 위와 같은 맵을 하나 만든다.set할 때에는 key, timestamp, value를 자료형 타입과 맞게 m에 넣어준다. get 할 때는 먼저 key값과 맞는 {timestamp, value}를 찾는다.만약 하나도 없다면 빈 스트링을 반환한다. 맞는 map이 있다면 해당 맵에서 upper_bound를 이용해 time.. 2019. 1. 31.
[Leetcode][954] Array of Doubled Pairs 문제 : https://leetcode.com/problems/array-of-doubled-pairs/ map을 하나 만든다. map의 key는 A 배열의 요소 값이 되고 value는 해당 값이 나온 횟수가 된다. A배열은 절대값 기준으로 오름차순 정렬한다. 문제를 보면 A[i]를 2배 한 값이 있는지만 체크하면 된다. A[i]를 1/2 한 값을 찾거나 *2 한 값을 찾아야 하기 때문에 절대값 오름차순 정렬을 함으로서 *2 한 값만 있는지 체크하기 위함이다. ex) A = {-4, 1, -2} 인 경우 정렬하지 않으면 1/2 (-2)도 체크하고 *2 (-8)한 값도 체크해야 한다. 절대값 기준 오름차순 정렬한다면 A = {1, -2, -4}가 될 것이기 때문에 *2한 값만 체크해도 된다. 값을 찾을 때.. 2018. 12. 21.
[Leetcode][931] Minimum Falling Path Sum 문제 : https://leetcode.com/problems/minimum-falling-path-sum/ DP로 풀었다.떨어지는 경로의 배열 합이므로 현재 위치에서 갈 수 있는 배열은 왼쪽 아래, 아래, 오른쪽 아래이다.따라서 점화식은 아래와 같이 만들 수 있다. d[i][j] = A[i][j] + min(d[i-1][j-1], d[i-1][j], d[i-1][j+1])cs 배열을 모두 돌며 배열 d를 채웠을 때 마지막 행에서 가장 작은 값이 정답이 된다. 시간복잡도는 A배열이 NxN이라 했을 때, O(N^2). 소스코드 : https://gist.github.com/fpdjsns/18f4d32c49ac294a4175065fc8cfca90 2018. 12. 18.
[Leetcode][958] Check Completeness of a Binary Tree 문제 : https://leetcode.com/problems/check-completeness-of-a-binary-tree/ 위 그림에서 보면 완전이진트리라면 배열에 저장될 때 현재 노드 인덱스(n) 기준으로 왼쪽 자식 노드는 2n 인덱스에, 오른쪽 자식 노드는 2n+1 인덱스에 저장된다.이를 이용하여 루트부터 자식노드들을 탐색하면서 노드가 저장되는 인덱스 중 최대 값을 구하고 총 노드 수를 구한다.만약 완전이진트리라면 인덱스의 최대값과 노드 수는 같을 것이고 완전이진트리가 아니라면 인덱스의 최대값이 노드 수보다 클 것이다. 시간 복잡도는 노드 수를 N이라 할 때 O(N). 소스코드 : https://gist.github.com/fpdjsns/f32430b2e112b79a5647bfdd7b7d30d7 2018. 12. 17.
[Leetcode][955] Delete Columns to Make Sorted II 문제 : https://leetcode.com/problems/delete-columns-to-make-sorted-ii/ ["ax", "ay", "ba", "bb"]를 입력값으로 예를 들어보면 1, 2행 "ax", "ay" 는 첫번째 열 a 가 같으므로 두 번째 열 x, y는 정렬이 되어야 한다.2, 3행 "ay", "ba" 는 첫번째 열 a, b 가 같지 않고 사전순정렬이 되어있기 때문에 두 번째 열 y, a는 정렬이 될 필요가 없다.(정렬되지 않아도 사전 순 정렬이 되기 때문에)위 개념으로 알고리즘을 생각해본다. A 요소 개수를 N, A[i]의 길이를 M이라 하자.N크기만큼의 bool형 배열(ordered)을 하나 만든다.ordered[i] = A[i-1], A[i] 는 사전순 정렬이 되어있는가.를.. 2018. 12. 16.
[Leetcode][948] Bag of Tokens 문제 : https://leetcode.com/problems/bag-of-tokens/ tokens 배열을 오름차순 정렬한다.tokens 배열의 앞에서부터 토큰을 power로 얻으면서 탐색해나간다. (앞으로 탐색중인 인덱스는 i, 토큰 배열 요소 값은 tokens[i]라 하자.)만약 탐색중에 남은 power로 tokens[i]를 얻을 수 없다면 토큰을 하나 돌려주고 가장 비싼 토큰(인덱스 r이라 하자. r의 초기값은 tokens 배열의 마지막 인덱스와 같다.)의 power부터 가져온다. (낮은 power로 큰 power를 얻은 것과 같다.)power를 가져온 뒤는 반드시 tokens[i]를 얻을 수 있다. 왜냐하면 인덱스는 i < r인데 오름차순 정렬했기 때문에 tokens[i] 2018. 12. 4.

티스토리툴바