j-engine 님의 블로그

이 문제는 배열이 주어졌을 때 배열에서 과반수를 차지하는 숫자를 찾는 것입니다.과반수를 차지하는 숫자는 배열의 절반 크기(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(..

이 문제는 Linked-List가 주어졌을 때 이 리스트가 Palindrome인지 확인하는 문제입니다.Palindrome이란 보통 'eye', 'madam', '다시합시다' 등과 같이 역순으로 읽어도 같은 말이나 구절 또는 숫자를 의미합니다.이를 List에 대입하면 거꾸로 읽어도 같은 구조를 의미할 수 있습니다. 아주 간단하게 생각하면 리스트를 역순으로 하나 생성한 뒤 원래 리스트와 비교해 같은지 확인하는 방법이 있습니다.하지만 조금 더 빠르게 할 수 있는 방법도 있습니다. Palindrome은 역순으로 읽어도 같기 위해 반으로 나누었을때 뒤의 절반을 역순으로 만들면 앞의 절반과 뒤의 절반의 역순이 같습니다. 쉽게 생각해서 중간을 기준으로 반으로 접을때 같으면 Palindrom이라는 의미입니다. 그래서 ..

이 문제는 Linked-List가 주어졌을 때 리스트에 Cycle이 존재하는지 찾는 문제입니다.Cycle이란 이전에 방문했던 곳을 연결된 노드를 타고 갔을 때 다시 방문하게 되어서 결국 계속해서 도는 구간을 의미합니다. 노드의 값에 음수도 존재하기에 unordered_map을 활용해 이전에 노드를 방문한 적이 있는지 확인해 재방문하는 것이라면Cycle로 판단하는 구조로 문제를 풀었습니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ bool hasCycle(ListNode ..

이 문제는 Linked-List에서 중간에 있는 노드를 찾아 반환하는 문제입니다.만약 배열이면 배열의 크기를 찾아 반으로 나눠 쉽게 중간값을 찾을 수 있습니다.하지만 Linked-List는 index가 아닌 포인터로 연결되어 있기에 포인터를 사용해야 합니다. 이때 Slow and Fast Pointer라는 걸 사용할 수 있습니다. 런너 기법이라고도 불립니다.Slow는 한 번에 한 칸씩 이동하는 포인터이고 Fast는 한 번에 두 칸씩 이동하는 포인터입니다.Slow 포인터가 한 칸 이동할 때 Fast 포인터는 두 칸 이동하므로 Fast 포인터가 Linked-List의 맨 마지막 노드혹은 nullptr에 도달하면 Slow 포인터는 Linked-List의 중간에 도달하게 됩니다. While Loop를 통해 Sl..

이 문제는 정수 배열이 NumArray 클래스를 초기화할 때 주어지면 이를 사용해 NumArray 클래스의 sumRange 함수를 완성하는 것 입니다.sumRange함수는 정수 left, right가 주어지면 이를 index로 활용해 left  가장 간단하게 풀려면 매번 sumRange가 호출될 때마다 loop를 돌며 값의 합을 구하면 됩니다.class NumArray {public: NumArray(vector& nums) :nums(nums) { } int sumRange(int left, int right) { int sum = 0; while (left nums;};/** * Your NumArray object will be instantiated and c..