Study Log

https://leetcode.com/problems/palindrome-linked-list/description/ 문제 문제 분석- Linked List의 값들을 다른 자료형에 옮겨서 양 끝을 하나씩 검사하는 방식으로 palindrome을 검사할 수 있을 것입니다. 양 끝에서만 접근이 이루어지기 때문에 Deque를 쓰는 것이 가장 효율적이라고 생각했습니다.- Runner 기법을 사용하여 구현한다면 모든 ListNode를 다른 자료형에 넣지 않고도 검사할 수 있을 것 입니다. 절반까지만 딱 읽어드리면서 그 절반을 reverse한 Linked List를 만들고, 이걸 남은 절반과 비교하면 됩니다. 풀이 1 (Deque)/** * Definition for singly-linked list. * struc..

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/문제 문제 분석1. 가장 작은 값을 계속 갱신해가며 profit을 구하면 됩니다. 배열 순서대로 진행하면 이전의 결과와 차이를 계산하지 않고 계속 배열 뒤쪽의 값들과만 계산할 수 있습니다. 풀이class Solution {public: int maxProfit(vector& prices) { int min = 10000; int profit = 0; for(const auto& price: prices){ if(price

https://leetcode.com/problems/product-of-array-except-self/description/ 문제 문제 분석1. 가장 빠른 풀이는 0이 2개 이상 나오는 경우 예외 케이스 처리해주고, 전체 곱을 구하고 각 요소로 나누는 것일 겁니다.하지만 문제 조건에 without using the division operation이라고 나와있기 때문에 이 방식은 옳지 않습니다.2. 왼쪽에서 시작해서 쭉 곱한 값과 오른쪽에서 시작해서 쭉 곱한 값을 구해서 두 배열 안의 값들을 매칭해서 곱하면 됩니다.즉, 해당 인덱스의 왼쪽에 있는 것들을 모두 곱한 값, 오른쪽에 있는 것들을 모두 곱한 값을 따로 구하고 두 값들을 곱해서 최종 값을 구하면 이는 본인을 제외한 나머지 값들을 모두 곱한 값..

https://leetcode.com/problems/array-partition/description/ 문제 문제 분석- (1, 2), (3, 4) 처럼 묶어서 min을 하게되면 결국 오름차순 정렬 후 짝수 번째(0 포함)에 있는 요소들의 합이 바로 결과가 됩니다. 풀이 1class Solution {public: int arrayPairSum(vector& nums) { sort(nums.begin(),nums.end()); for(int i=1;i

https://leetcode.com/problems/3sum/description/ 문제 문제 분석1. Brute force를 이용하면 문제는 풀리긴 하겠지만 분명 시간 초과가 날 것이라 생각했습니다.2. 정렬을 한 뒤에 Two pointer를 사용하는 방식을 생각했습니다. 기준 숫자, 기준 숫자 + 1 (left), 배열의 끝(right)에서 시작을 하여 이 합이 0보다 작다면 left를 이동시키고, 0보다 크다면 right를 이동시키는 방식을 이용하면 보다 효율적으로 계산할 수 있습니다.3. 같은 숫자를 가진 것에 대해서는 또 계산할 필요는 없기 때문에 건너뛰도록 하였습니다. 이외에도 배열 사이즈가 3보다 작던가, 이미 더이상 계산하는 것이 무의미한 케이스들에 대해서 검사하여 불필요한 계산을 줄이도..

https://leetcode.com/problems/trapping-rain-water/description/문제 문제 분석1. BruteForce로 검사하면 물론 답은 나오겠지만, 시간초과가 날 것입니다.2. Two Pointer를 사용하는 방법. 물이 담기는 경우에는 항상 작은 것을 기준으로 담깁니다. 맨 왼쪽과 맨 오른쪽부터 시작하면서 가장 큰 블럭에 도달할 때까지 이동하면서 계산을 합니다. 가운데에 어떤 블럭이 있는지 모르는 상태에서 하나씩 접근해가면서 현재 왼쪽의 최댓값보다 오른쪽 블럭의 최댓값이 더 크다면 현재 위치에서 담길 수 있는 물의 양은 (왼쪽의 블럭 최댓값) - (왼쪽의 현재 위치의 블럭)이고, 왼쪽으로 포인터를 한 칸 이동시키면 됩니다. 오른쪽 관점도 마찬가지입니다.3. 스택을 이..

https://leetcode.com/problems/two-sum/description/문제문제 분석- bruteforce로도 풀 수 있겠지만, 실행 시간을 줄이기 위해서 하나의 숫자를 고르고, Target 값에서 그 숫자를 뺀 값을 찾는 방식으로 푸는 것이 낫다고 생각하였습니다. 풀이 1#include #include using namespace std;class Solution {public: vector twoSum(vector& nums, int target) { for (int i = 0; i (iter - nums.begin())}; } } return {}; }};vector를 그대로 find로 하나씩 둘러보면서 찾으니 시..

https://leetcode.com/problems/longest-palindromic-substring/description/문제 문제 분석- 문자열을 직접 잘라서 하나씩 조사하는 것보다 포인터를 두 개를 두어서 중심을 기준으로 늘려가는 것이 효율적이라고 판단하였다. 풀이class Solution {private: string origin; int length; string expand(int left, int right){ while (left >= 0 && right = temp_2.length()){ if(temp_1.length() >= result.length()) result = temp_1; ..

https://leetcode.com/problems/group-anagrams/description/ 문제 문제 분석- 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것이 anagram. 즉, 여기서는 anagram 관계를 가지는 것들을 모아서 반환하라는 것입니다.- anagram 관계에 있는 문자열들을 정렬하면 같은 문자열이 나올 것이기 때문에 이를 활용하면 될 것이라고 생각했습니다.(ex. ate -> aet, eat -> aet, tea -> aet)- 정렬 후 나온 문자열에 대해서 빠른 접근이 가능하도록 hash를 사용한 unordered_map을 사용하는 것이 좋다고 생각했습니다. key를 정렬 후 나온 문자열, value로 string vector를 가지고 있고 value에 계속 추가하는 ..

문제 문제 분석- 주어진 문자열 중에서 가장 많이 나온 단어를 찾는다. (banned에 있는 단어를 제외하고)- unordered_map으로 관리하는 것이 제일 효율적이라고 생각하였다. - 정규표현식을 사용하고 소문자로 통일시켜서 전처리를 한 다음에 단어 개수를 세면된다고 생각하였다.- banned에 있는 단어인지 하나씩 검사하고 처음부터 아예 안넣는 방식과 나중에 가장 많은 단어를 구할 때만 제외하는 방식 중 전자가 더 효율적이라고 생각하였다. 주어진 입력값에 따라 달라지겠지만 주어진 paragraph의 단어 수가 많아질 수록 매번 banned에 있는지 검사하는 것은 비효율적이라고 생각했기 때문이다. 하지만 전자의 방식을 unordered_set을 사용하면 일반적으로 O(1)에 find를 할 수 있기 ..