Study Log

https://leetcode.com/problems/reverse-linked-list-ii/description/ 문제 문제 분석- Linked list 뒤집기 문제에서 범위만 따로 추가된 것입니다. left에 해당하는 범위까지 이동한 뒤에 배열을 쭉 뒤집고, right 이후에는 그대로 이어붙여주면 됩니다. 풀이/** * 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..

https://leetcode.com/problems/odd-even-linked-list/description/ 문제 문제 분석- 임시 변수를 몇 개 사용하는 것은 O(1) extra space에 해당됩니다. 그러나 입력 크기에 비례하여 새로운 배열이나 리스트를 생성한다면, 이는 O(n) 이상의 공간 복잡도를 필요로 하기에 이 문제에서는 불가능 합니다.- odd와 even을 따로 관리하고 even의 시작 노드를 마지막에 odd의 끝에 이어붙여주면 됩니다. 풀이/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr)..

https://leetcode.com/problems/swap-nodes-in-pairs/description/ 문제 문제 분석- 값만 바꾼다면 쉽겠지만, 문제에서 노드 자체를 바꾸라고 하였습니다. 재귀 또는 반복으로 이를 구현할 수 있습니다. 풀이1 (재귀)/** * 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) {} ..

https://leetcode.com/problems/add-two-numbers/description/ 문제 문제 분석- 예시 1과 같이 342 + 465를 계산하는 것이므로 가산기를 구현하였습니다. 역순으로 되어있기에 carry를 그대로 다음 라운드에서 이용할 수 있습니다. 계산 후 값을 결과에 넣을 때만 역순으로 넣어주면 됩니다. 풀이/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(i..

https://leetcode.com/problems/reverse-linked-list/description/ 문제 문제 분석- 재귀를 이용해서, 또는 반복문을 이용해서 풀 수 있습니다. 풀이 1 (재귀)/** * 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:..

https://leetcode.com/problems/merge-two-sorted-lists/description/ 문제 문제 분석- list1과 list2의 각 요소들을 하나씩 비교해서 작은 것들을 먼저 결과에 넣습니다. 그 다음에 남은 리스트가 있다면 통째로 연결합니다. 풀이/** * 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), ne..

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