Study Log

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) {} ..

https://leetcode.com/problems/add-two-numbers/description/ 문제 문제 분석- 예시 1과 같이 342 + 465를 계산하는 것이므로 가산기를 구현하였습니다. 역순으로 되어있기에 carry를 그대로 다음 라운드에서 이용할 수 있습니다. 계산 후 값을 결과에 넣을 때만 역순으로 넣어주면 됩니다. 풀이/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(i..

https://leetcode.com/problems/reverse-linked-list/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) {} * }; */class Solution {public:..

https://leetcode.com/problems/merge-two-sorted-lists/description/ 문제 문제 분석- list1과 list2의 각 요소들을 하나씩 비교해서 작은 것들을 먼저 결과에 넣습니다. 그 다음에 남은 리스트가 있다면 통째로 연결합니다. 풀이/** * 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), ne..