이 문제는 배열이 주어졌을 때 배열에서 과반수를 차지하는 숫자를 찾는 것입니다.과반수를 차지하는 숫자는 배열의 절반 크기(n/2)보다 많습니다. 가장 간단하게 풀 수 있는 방법은 정렬을 한 뒤 Index = n / 2에 있는 수를 반환하는 것입니다.과반수를 차지하는 숫자를 찾는 것이므로 정렬을 하면 배열의 중간에 과반수를 차지하는 수가 오기에 간단하게 답을 찾을 수 있습니다. int majorityElement(std::vector &nums) { std::sort(nums.begin(), nums.end()); return nums[nums.size() / 2]; }이 방법은 정렬하는 시간으로 인해 평균 시간복잡도 O(N log N)의 시간을 가집니다. Hash..

숫자 배열이 주어지면 이 배열 안에서 만들 수 있는 연속된 부분 배열들 중 가장 큰 부분 배열의 평균값을 찾는 문제입니다.만약 [1, 12, -4, -6] 배열이 있으면 부분 배열은 연속적으로 만들어져야 하므로 [1, 12]나 [12, -4, -6]과 같은 부분 배열은 가능하나 [1, -4]와 같이 떨어져 있는 원소들은 부분 배열로 만들 수 없습니다.가장 큰 평균값을 찾는 것이므로 부분 배열의 원소의 수로 나누기 전 원소들의 합이 가장 큰 부분 배열을 찾으면 됩니다.이때 문제에서 주어진 부분 배열의 길이는 k입니다.즉, 부분 배열의 길이가 k인 배열의 원소들의 합이 가장 큰 경우를 찾으면 됩니다. 생각나는 가장 간단한 방법은 모든 부분 배열을 시도해보는 것입니다.  double findMaxAver..

이 문제는 Linked-List를 뒤집는 문제입니다. 이전 노드, 현재 노드, 다음 노드를 각각 추적하며 각 노드가 가르키는 방향을 바꿔줍니다./** * 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: ListNode* reverseList(ListNode*..

이 문제는 날짜 별로 주식의 가격이 적힌 배열이 주어집니다.그러면 어떤 날에 주식을 산 후 다른 날에 주식을 팔 때 가장 큰 이익이 얼마인지 찾는 문제입니다. 간단하게 하루하루가 지날 때마 가장 가격이 낮을 때를 사는 날로 정하고 가장 낮은 가격을 갱신해줍니다.이때 갱신한 날이 주식을 산 날입니다.이루 하루가 지날때마다 가장 낮은 가격을 빼 이득을 계산하며 최대 이득을 갱신해줍니다.  int maxProfit(vector& prices) { int profit = 0; int minPrice = prices[0]; // 첫날은 팔 수 없습니다. for (int i = 1; i

정렬된 Linked-List가 주어질 때 중복된 값을 가진 노드들을 삭제하는 문제입니다. 만약 다음(next) 노드가 현재 노드의 값과 같은 값을 가지면 두 노드는 중복된 것 입니다.중복된 노드를 유일한 노드로 만들어야 하므로 다음 노드를 삭제하고 그 다음 노드에 현재 노드의 next를 연결합니다.이 과정을 List의 끝까지 반복하면 중복된 노드들을 지울 수 있습니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {}..

이 문제는 Linked-List에서 원하는 값을 전부 삭제해야하는 문제입니다. 찾는 값이 리스트 중간에 있는 경우 이전 노드의 next를 다음 노드에 연결한 다음 현재 노드를 삭제합니다.즉, 이전 노드를 추적하는 포인터가 필요합니다.또한, 만약 찾는 값이 중간이 아닌 맨 앞에 있으면 이전 노드를 추적할 필요 없이 head를 다음 노드로 만들고 맨 앞 노드였던 노드를 삭제해줍니다. 이렇게 두 과정을 차례대로 진행해주면 되는데 먼저 맨 앞에 있는 경우를 처리하고 리스트 중간에 있는 경우를 처리해주면 됩니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(..