Study Log

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/ 문제 문제 분석- DFS 재귀 탐색을 이용해서 가능한 모든 경우의 수를 만들어내면 됩니다.- 각 순서가 유지되기 때문에 단순 DFS로 풀이가 가능합니다. ("23"이면 "32"인 경우랑은 다름) 풀이class Solution {private: std::map> keypad = { {2, {'a', 'b', 'c'}}, {3, {'d', 'e', 'f'}}, {4, {'g', 'h', 'i'}}, {5, {'j', 'k', 'l'}}, {6, {'m', 'n', 'o'}}, {7, {..

https://leetcode.com/problems/number-of-islands/description/ 문제 문제 분석- 입력값을 동서남북이 모두 연결된 그래프로 가정하고 각 방향에 대해서 DFS 재귀를 이용해서 탐색이 끝나면 전체 섬의 개수를 1 증가시키는 방법으로 섬들을 탐지할 수 있습니다.- 방문 여부를 따로 트래킹하거나 '1'을 '0'으로 바꾸는 방법을 사용할 수 있습니다. 풀이 1 (방문 여부 트래킹)class Solution {private: vector> isVisited; vector> *grid; int row; int col; int count;public: void dfs(int i, int j){ if(i = row || j >= c..

https://leetcode.com/problems/design-hashmap/description/ 문제 문제 분석- 개별 체이닝 방식으로 hashMap을 구현하였습니다 풀이class MyHashMap {private: static const int SIZE = 1000; struct Node{ int key; int value; Node* next; Node(int k, int v):key(k), value(v), next(nullptr){} }; vector map;public: MyHashMap() { map.resize(SIZE, nullptr); } void put(int key, in..

https://leetcode.com/problems/merge-k-sorted-lists/ 문제 문제 분석- priority queue를 이용해서 정리한 뒤, 요소를 하나씩 빼서 연결시키면 됩니다.- 어떤 방식으로든지 정렬을 해서 하나씩 뽑아서 넣으면 됩니다. 풀이class Solution {public: ListNode* mergeKLists(vector& lists) { if (lists.empty()){ return nullptr; } auto compare = [](ListNode* a, ListNode* b){ return a->val > b->val; }; std::priority_qu..

https://leetcode.com/problems/daily-temperatures/description/ 문제 문제 분석- 스택을 이용해서 온도와 index를 같이 저장해놓고, stack의 top과 현재 temperature를 비교해서 현재가 더 높은 경우에는 stack에서 제거한 뒤 result에 해당하는 index에 Index - 현재 index를 기록합니다. 현재 temperature가 더 높다면 계속 반복합니다. 풀이class Solution {public: vector dailyTemperatures(vector& temperatures) { vector> stack; vector result(temperatures.size(), 0); stack..

https://leetcode.com/problems/remove-duplicate-letters/description/ 문제 문제 분석사전식 순서라는 것을 잘 이해해야 합니다. string을 구성하는 각 char들을 a,b,c .. 이런 식으로 전부 오름차순하라는 것이 아니라 중복을 제거한 상태에서 나올 수 있는 string 중에서 사전순으로 앞선 string을 반환하라는 것입니다.예를 들면, dacbbc라는 글자가 있을 때 중복 제거시 나올 수 있는 경우는 dacb, dabc가 있습니다. 이때 사전 순으로는 dabc가 dacb보다 앞서 있기때문에 dabc를 반환해야 합니다.d가 a보다 사전순으로 뒤에 있는 것은 맞지만, 각 요소를 사전순으로 배치하라는 것이 아닌 중복을 제거한 문자열 경우의 수 중에서..

https://leetcode.com/problems/valid-parentheses/description/ 문제 문제 분석- 스택을 이용해서 닫는 기호가 나타났을 때, 스택의 가장 최상단에 그와 연결되는 여는 기호가 있어야 유효한 Parenthesis가 될 수 있습니다.  풀이class Solution {private: map match = { {')', '('}, {'}', '{'}, {']','['} };public: bool isValid(string s) { stack stack; for(const auto& c: s){ if(c == '(' || c == '{' || c == '['..

https://leetcode.com/problems/reverse-linked-list-ii/description/ 문제 문제 분석- Linked list 뒤집기 문제에서 범위만 따로 추가된 것입니다. left에 해당하는 범위까지 이동한 뒤에 배열을 쭉 뒤집고, right 이후에는 그대로 이어붙여주면 됩니다. 풀이/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode..

https://leetcode.com/problems/odd-even-linked-list/description/ 문제 문제 분석- 임시 변수를 몇 개 사용하는 것은 O(1) extra space에 해당됩니다. 그러나 입력 크기에 비례하여 새로운 배열이나 리스트를 생성한다면, 이는 O(n) 이상의 공간 복잡도를 필요로 하기에 이 문제에서는 불가능 합니다.- odd와 even을 따로 관리하고 even의 시작 노드를 마지막에 odd의 끝에 이어붙여주면 됩니다. 풀이/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr)..

https://leetcode.com/problems/swap-nodes-in-pairs/description/ 문제 문제 분석- 값만 바꾼다면 쉽겠지만, 문제에서 노드 자체를 바꾸라고 하였습니다. 재귀 또는 반복으로 이를 구현할 수 있습니다. 풀이1 (재귀)/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} ..