메모장 메모장

class Solution { public: int longestConsecutive(vector& nums) { int answer = 0; unordered_set s(nums.begin(),nums.end()); for(int n : nums) { if(s.find(n-1) == s.end()) { int now = n; int matched = 1; while(s.find(now + 1) != s.end()) { now += 1; matched++; } answer = max(answer, matched); } } return answer; } }; 결과를 확인해보니 최적은 아닌것 같지만, 우선 set을 활용하여 간단하게 풀어보았습니다. union-find를 구현하는 문제인데 o(n)에 구현해야되..

오늘은 트리에 대해서 알아보려고 합니다. 해당 내용은 종만북을 공부하고 정리한 내용입니다 ✔︎ 트리 란 ? 계층적 구조를 갖는 자료들을 표현하기 위한 자료구조 주로 노드를 구조체로 표현하고 자식 노드를 포인터로 연결 ✔︎ 순회 계층적 구조를 갖는 트리의 노든 노드를 확인하는 것은 중요 이를 순회라고 하며 주로 재귀적 속성을 활용해서 진행 ⁃ 전위순회 : 부모 -> 왼쪽 자식 -> 오른쪽 자식 ⁃ 중위순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식 ⁃ 후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모 [ 대표문제 ] 트리 순회 순서 변경 전위순회 + 중회순회 주어졌을떄 후위순회 결과 출력 void printPostOrder(const vector& preorder, const vector& postord..

class Solution { public: bool DFS(vector& rooms, vector& visited, int now, int& chked){ bool ret = false; if(visited[now]){ return ret; } if(chked == rooms.size() - 1) return !ret; visited[now] = 1; chked++; for(int i:rooms[now]){ ret = ret | DFS(rooms, visited, i, chked); } return ret; } bool canVisitAllRooms(vector& rooms) { vector visited(rooms.size(), 0); int chked = 0; return DFS(rooms, vis..

class Solution { public: int mvI[4] = {0,0,-1,1}; int mvJ[4] = {1,-1,0,0}; int DFS(int i, int j, vector& grid, vector& visited){ int ret = 1; if(visited[i][j]) return 0; visited[i][j] = true; bool goFlag = false; for(int k=0; k= grid[0].size()) continue; if(!grid[newI][newJ]) continue; goFlag = true; ret += DFS(newI, newJ, grid, visited); } } return goFlag ? ret : 0; } int countServers(vector& g..

leetcode 답게 문제에서 요구하는 바는 간단했습니다. DAG가 주어졌을떄, 각 노드에서 경로를 따라 도달할 수 있는 노드들의 리스트를 구하고 이렇게 구한 리스트들을 최소한으로 조합하여 모든 노드들을 커버하는 케이스를 구하라는 것이다., 음,, 우선 각 노드에서 도달할 수 있는 노드들의 리스트를 구해야 했으니 플로이드 와셜 알고리즘이 떠올랐다. 떠오르자 마자 해당 알고리즘을 쓰면 소스가 무지하게 더럽게 나올 것 같단걸 예상했지만 우선 시도해보았습니다., 역시 더럽더군요,,, 중간에 포기하고 새로운 아이디어를 생각해보다가 그냥 단순히 들어오는 경로가 없는 노드들을 출력하면 되는 거였더군요 어차피 들어오는 경로가 없는 노드들은 필연적으로 답에 포함되는 노드들이기 때문에 들어오는 경로가 없는 노드들만을 조..

배열이 주어졌을때 어느영역만큼을 정렬하면 전체가 정렬된 상태일지 출력하는 문제이다. 가장 간단한 방식으로 접근해보면, 기존의 배열과 정렬된 배열을 양끝의 인덱스부터 비교하면서 서로 틀어지는 부분의 영역을 출력해주면 정답이 된다. 시간복잡도는 정력작업으로 인해 O(nlogn)이라서 수행속도를 보면 별로 빠르지 않다. class Solution { public: int findUnsortedSubarray(vector& nums) { if(nums.size() == 1) return 0; vector numsCpy = nums; sort(numsCpy.begin(), numsCpy.end()); int left = 0; int right = nums.size() - 1; while(left < right){..

간만에 하드 문제를 풀어보았다. 문제를 보고선 바로 아래와 같은 풀이를 생각했다. 타임아웃이 예상되었지만, 자비로운 리트코드기에 굉장히 떨어지는 성능으로 통과 시켜줄거라 생각햇지만,, 역시 실패 소스 보시면 아시겠지만 단순하게 우선순위큐를 계속 생성해서 max 값을 리턴하게 해두었다. class Solution { public: vector maxSlidingWindow(vector& nums, int k) { vector ret; for(int i = 0; i = k - 1){ ret.push_back(que.front()); if(que.front() == nums[i - k + 1]){ que.pop_front(); } } } return ret; } }; while문에서 최악의 경우 시간을 좀 잡..

class Solution { public: int removeDuplicates(vector& nums) { int size = nums.size(); for(int i = 0; i 0 && nums[0] == tmp){ i++; nums.erase(nums.begin()); } nums.push_back(tmp); i--; } return nums.size(); } }; 인라인으로 풀라는 조건이 있길래 생각나는대로 배열 뒤에 원소를 붙이고 지나간 원소들은 삭제처리했다. 중간중간에 계속 삭제처리를 해서 타임아웃을 예상했는데 아슬아슬하게 통과되었다. discuss를 보니 좀 더 효율적인 방법이 있던데 아래와 같다. 내 소스가 훨씬 직관적!!! 이라고 말하고 싶다만 역시 효율적인 아래소스가 정해로 보인다...