귤귤나무 일지

딱히 알고리즘이랄 것 없이 그냥 각 list의 값을 비교하면서 더 작은 값을 반환 값의 next로 이어 붙임.한 list가 다른 list보다 먼저 끝나면 다른 list의 남은 node들을 반환 값에 append함./** * 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 {pub..

유명한 문제로 stack 사용해서 풀면 된다.여는 괄호가 나올 때는 다 stack에 넣고 닫는 괄호가 나왔을 때는 stack의 top과 매칭되면 stack pop을 하고 매칭되지 않으면 false를 반환한다.class Solution {public: bool isValid(string s) { stack valid_brackets; for (auto i: s) { if (i == '(' || i == '[' || i == '{') valid_brackets.push(i); else { if (valid_brackets.empty()) ..

처음 풀이는 첫 번째 단어를 기준으로 삼아서 다음 단어들과 비교한다.첫 번째 단어의 각 문자와 다음 단어들의 해당 위치 문자가 모두 동일한지 확인 후, 동일하지 않을 경우 바로 break해서 반환하도록.class Solution {public: string longestCommonPrefix(vector& strs) { if (strs.size() == 1) { return strs[0]; } int i; bool flag = false;; for (i = 0; i 그리고 해설을 보니까 이렇게 break해서 flag 설정 후 반환할 필요 없이 바로 반환하면 되는 거였다.class Solution {public: ..

처음 풀이.주어진 vector를 정렬해서 min값, max값을 찾고,find를 사용해서 앞에서부터 첫 min값까지의 거리(index), 뒤에서부터 첫 max값까지의 거리를 찾고,min이 max보다 뒤에 있으면 둘 더한 값에 -1(테스트케이스 1의 경우처럼 min값이 한 칸 앞으로 올 수 있음),min이 max보다 앞에 있으면 그냥 둘 더한 값을 반환.class Solution {public: int minimumSwaps(vector& nums) { vector tmp_num = nums; sort(tmp_num.begin(), tmp_num.end()); int min_num = tmp_num[0]; int max_num = tmp_num[tmp_..

비슷한 문제로 프로그래머스에 있는.. 그 기능개발 문제가 생각났다.근데 그때는 시간 단위가 작았던 것 같아서 시간을 1씩 증가시키면서 반복문을 돌아서 조건 체크를 했다.이번 문제는 좀 다른 방식으로 접근했다.처음에 들었던 생각은..1. 일단은 시작 시간 순서로 오름차순으로 정렬해야겠다!2. 그런 다음에 방 개수를 저장하듯이 배열에 각 회의의 끝나는 시간을 저장해야겠다.3. 단 끝나는 시간도 오름차순으로 정렬해야겠다!4. 다음 회의가 들어오면 그 회의의 시작 시간과, 이미 진행중인 회의들의 끝나는 시간 중 가장 작은 시간을 비교해서 pop/push하기class Solution {public: int minMeetingRooms(vector>& intervals) { sort(interva..

많이 봤던 문제 유형이다.bfs 사용해서 풀면 될 것 같아서 구현했다.conttinue할 조건 설정하는 데 디버깅 조금 걸렸다.class Solution {public: int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, -1, 1}; int m, n; int numIslands(vector>& grid) { m = grid.size(); n = grid[0].size(); vector> visited (m, vector(n, false)); queue> q; int answer = 0; for (int i = 0; i cur = q.front(); ..

처음에는 vector와 해시맵을 사용해서 구현했다.vector에는 key들을 우선순위 순서대로 넣고(우선순위 높은 게 앞으로),해시맵에는 해당 key에 대한 value를 저장했다.class LRUCache {public: int cap; vector cache_key; unordered_map cache_map; LRUCache(int capacity) { this->cap = capacity; } int get(int key) { //get한 key 우선순위 높이기 auto it = find(cache_key.begin(), cache_key.end(), key); if (it == cache_key.end()) ..

우선 내가 생각한 풀이.예제 3처럼 동일한 val을 가지는 값이 존재할 수 있어서, 값만으로 해당 node를 찾기는 어렵다.그래서 생각한 게 우선 linked list를 생성해서 val은 다 동일하게 맞추고, random은 이후에 맞추자!random을 이후에 맞출 때 어떤 노드를 가리키는지 알기 위해 기존 list의 val을 index값으로 바꾼다./*// Definition for a Node.class Node {public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; }};*/class Solution {pu..

애너그램 찾기.처음에는 strs 안에 있는 값들을 정렬할까 했는데, 기존 값을 유지해야돼서 패스.다음에 생각한 풀이로는 set을 만들어서 set이 동일한지 비교하기.구현해봤으나 중복 문자가 있는 경우도 있어서 이 경우 실패했다.그래서 생각한 방법은 map을 사용해서 각 str이 저장하고 있는 알파벳 개수를 저장하고 map끼리 비교!class Solution {public: vector> groupAnagrams(vector& strs) { vector> maps; vector> answer; for (auto i: strs) { map tmp; for (auto j: i) { if (tmp.fin..

문제가 의미하는 것을 생각하는데 한 10분 정도 걸린 것 같다.매회마다 array에 있는 가장 작은 수보다 작거나 같은 값 x를 선택한 후, array의 모든 양수인 값에서 x를 빼라는 것은..작거나 같은 값을 선택하라고 하지만, 최소로 실행하려면 같은 값을 선택해야 한다.또한, 매회마다 array의 모든 양수에서 x를 빼는데, 이건 결국 매회마다 최소 값들을 제외하는 것과 같은 의미이다.왜냐하면 매회 최소값을 빼더라도, 그보다 큰 값을 0으로 만들 수는 없기 때문이다. 이걸 생각해낼 때 예제에서 주어진 array에 중간 값을 추가했을 때는 어떻게 될지, 더 큰 값을 추가했을 때는 어떻게 될지를 생각해봤다.[1, 5, 0, 3, 5] -> [0, 4, 0, 2, 4] -> [0, 2, 0, 0, 2] -..