hwooo

https://leetcode.com/problems/group-anagrams/description풀이1차문자열을 정렬한 후, 해당 값과 원래 값을 우선순위 큐에 저장.정렬한 값을 비교하며 같은 값이라면 벡터에 넣어 저장하는 방식으로 구현함 2차1차 풀이가 느려서 다른 풀이를 봤고, 정렬 값 비교를 우선순위 큐가 아닌 unordered_map으로 바꿈 3차2차입력 값의 범위가 소문자 영어로 국한되어 있어 sort 함수 대신 문자의 개수를 세서 정렬하는 방식으로 바꿨으나 2차보다 값이 느리게 나왔다.코드 - 1차 풀이class Solution {public: vector> groupAnagrams(vector& strs) { vector> anagrams..

https://leetcode.com/problems/open-the-lock/description/ 풀이 BFS로 순회하며 최단 거리를 찾는다. 이 때 해당 숫자에서 나올 수 있는 8가지 경우 (4자리, 각 자리 +-)를 모두 순회 이 때 순회한 숫자들은 순회했던 시간을 같이 저장, 그 이후에 해당 숫자에 접근하는 경우는 탐색하지 않음 시작 지점 = target인 경우 & deadends인 경우 예외 처리 코드 class Solution { private: #define INF 10000 public: int openLock(vector& deadends, string target) { int time[10000]; queue q; // init fill(time, time + 10000, 0); //..

https://leetcode.com/problems/car-pooling/description/ 풀이 imos 누적합을 사용, 사람이 가장 많이 탔을 때와 입력 받은 capacity 값 비교 후 답 도출 코드 class Solution { public: bool carPooling(vector& trips, int capacity) { int load[1001]; int maxPassengers = -1; // 0으로 초기화 fill (load, load + 1001, 0); // imos 누적합 for(int i = 0; i < trips.size(); i++) { int numPassengers = trips[i][0], start = trips[i][1], end = trips[i][2]; loa..

https://leetcode.com/problems/lru-cache/description/ 풀이 큐와 unordered_map을 사용했다. um : 문제에서 주어지는 key-value값을 저장 큐 : 실행되는 순서대로 큐에 저장 usedTime (map): 마지막 실행 시간 갱신 큐에는 중복 상관 없이 실행된 순서대로 값을 계속 넣는다, 이 때 usedTime 값과 큐의 시간이 같다 = LRU 이므로 해당 값을 um에서 뺐다. Example 1 예시 더보기 코드 class LRUCache { public: int cnt = 0, size; queue q; unordered_map um, usedTime; LRUCache(int capacity) { new unordered_map(capacity); ..

https://leetcode.com/problems/gas-station/ 풀이 다른 분의 풀이를 보고 풀었다. gas[i] - cost[i] 까지는 생각했지만 for문 중간의 조건문을 생각하지 못 해서 답을 구하지 못 했다. 또 현재 가스량이 음수가 되었을 때가 답이 안 된다는 건 알았지만, 다음 인덱스부터 탐색할 때가 답이 될 수 있는지에 대해서도 의문이 많았다. 정확히는 아직도 잘 모르겠지만 답이 존재한다면 하나만 존재함이 보장됨 & 해당 인덱스 전의 값은 다 답이 될 수 없음의 이유가 아닐까 싶다 코드 class Solution { public: int canCompleteCircuit(vector& gas, vector& cost) { ios_base::sync_with_stdio(false)..

https://leetcode.com/problems/insert-delete-getrandom-o1/submissions/ 풀이 처음엔 벡터로만 이용해서 풀었으나 랜덤한 인덱스에 접근하는 방법을 모르겠어서 답을 봤다.답에서는 벡터와 unordered_map을 사용했다.벡터를 사용해서 값 삽입, 삭제, 인덱스로 접근을 했고, unordered_map을 이용해서 값을 탐색했다. 코드 class RandomizedSet { private: vector v; unordered_map m; public: RandomizedSet() { } bool insert(int val) { if (v.size() && m.find(val) != m.end()) return false; v.push_back(val); m[..

https://leetcode.com/problems/add-one-row-to-tree/ 풀이 bfs로 트리를 탐색, 넣어야 할 위치 바로 노드를 만났을 때 새로운 노드를 삽입해 줬다. 이 때, depth가 1인 경우는 따로 예외처리를 해 줬다. 코드 typedef pair pp; class Solution { public: TreeNode* addOneRow(TreeNode* root, int val, int depth) { queue q; q.push({root, 1}); // depth 1일 때 예외처리 if (depth == 1) { TreeNode *newRoot; newRoot = new TreeNode(val, root, NULL); return newRoot; } while (!q.emp..

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/ 풀이 현재 노드까지의 합을 저장하고, 자식 노드를 탐색할 때 이 합을 전달해주는 방식으로 풀었다. 트리 탐색이라 BFS, DFS 둘 다 될 것 같아서 두 방법 다 풀어보았다. DFS가 조금 빠른 것 같아 보였지만 이 정도의 차이는 유의미하지 않다고 들어서 큰 차이는 없을 것 같다. 코드 1 - BFS 6ms, 11.4MB typedef pair node; class Solution { public: int sumNumbers(TreeNode* root) { queue Q; int sum = 0; // 현재 노드와 현재 노드까지의 합을 큐에 저장 Q.push({root, 0}); whi..