Problem Solving/Leet Code (15) 썸네일형 리스트형 2134 Minimum Swaps to Group All 1's Together II Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Weekly Contest 275에 위치한 4점짜리 문제이다. 이 문제는 Medium 난이도답게 어렵게 생각할 필요 없이 직관적으로 두 단계를 거치면 해결할 수 있는 문제이다. 1. 배열에서 '1'의 개수 세기 2. 배열을 순회하며 각 지점에서 1이 연속적으로 위치하려면 얼마나 swap이 필요한지 세기 2번 단계의 경우 단순한 브루트 포스 방식으로 해결하면 시간이 오래 걸릴 수도 있지만 .. 55 Jump Game Jump Game - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 배열의 i번째 위치에 도달할 수 있다면 i 이전의 모든 위치를 지날 수 있다는 점을 이용하면 간단하게 풀 수 있다. 솔직히 그냥 위 생각만 가지고 의식의 흐름으로 대충 풀었을 때 그냥 풀리는 수준의 난이도라 개인적으로 왜 Easy가 아니고 Medium인지 이해가 안 되는 문제였다. 더보기 더보기 class Solution { public: vector check; vector vec; bool .. 1723 Find Minimum Time to Finish All Jobs https://leetcode.com/contest/weekly-contest-223/problems/find-minimum-time-to-finish-all-jobs/ 처음에 비트맵에 DP로 풀었다가 C++은 아슬아슬하긴 해도 통과하지만, 파이썬은 바로 시간 초과 나길래 그냥 Discussion에서 훌륭한 풀이를 가져왔다. https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/discuss/1042898/Most-performant-C%2B%2B-so-far-beats-100-runtime-99-memory C++ 더보기 class Solution { public: int minimumTimeRequired(vector& inputJob.. 1722 Minimize Hamming Distance After Swap Operations source를 조합해서 만드는 배열들과의 target 사이의 Hamming Distance들 중, 최솟값을 찾는 문제이다. 얼마나 Swap 연산을 수행하던지 상관없기에 source의 각 위치에서 DFS를 통해 target에서 가능한 모든 부분을 방문하고, 방문하지 못한 위치들의 수가 Minimum Hamming Distance가 된다. 그리고 이 문제에서는 target의 원소가 중복될 수 있으므로 방문 여부를 확인할 때 인덱스를 이용했으며, Hamming Distance를 구할 때에는 Unordered map을 이용했다. 여담이지만, 이거 난이도가 왜 Medium인지 모르겠다. 보통 DFS 문제처럼 직관적으로 풀리면 모르겠는데, 그것도 아니고 중복되는 원소도 있고 Hard가 적당한거 같은데 Discuss.. 1721 Swapping Nodes in a Linked List 링크드 리스트에서 두 개의 노드를 교체하는 것을 구현하는 문제이다. 리스트의 앞에서 k번째, 뒤에서 k번째의 노드를 교체해야 하는데, 리스트의 맨 앞에서부터 리스트를 순회하면서 앞에서 k번째, 뒤에서 k번째 노드의 포인터를 저장하고, 각 포인터에 저장된 값을 교환하는 식으로 구현하였다. C++ 더보기 /** * 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).. 1720 Decode XORed Array encode 배열의 N번째 원소와 decode 배열의 N - 1번째 원소와 XOR 연산을 수행해 encoded 배열의 N번째 원소를 만들어 주면 된다. 전에 XOR 연산과 Trie 이용해서 푸는 1707 때문에 살짝 트라우마 왔었는데, 생각할 거리도 없이 무척 간단하게 풀었다. 더보기 class Solution { public: vector decode(vector& encoded, int first) { vector res; res.push_back(first); int i = 0; for(auto v : encoded) res.push_back(v ^ res[i++]); return res; } }; 더보기 class Solution: def decode(self, encoded: List[int],.. 239 Sliding Window Maximum 주어진 배열에서 window를 한 칸씩 옯겨가며 window의 최대 원소를 반환하는 문제이다. 입력이 크기 때문에 문제 이름대로 sliding window 방식으로 풀면 당연히 시간 초과가 나버린다. 그래서 이 문제에서는 앞, 뒤로 push, pop 연산을 수행할 수 있는 deque를 사용해야한다. deque로 배열을 순회하며 새로운 원소들을 넣어주는 데, 이때 새로 집어넣어 줄 원소가 deque의 원소보다 크면 deque를 완전히 비워준다. 그리고 deque에는 매번 window로 참조하지 않는 원소가 포함되면 그것도 빼주어야 하고 이를 위해 deque에는 배열의 인덱스를 넣어준다. 말로 적으면 간단하지만 첨할 때는 예외 처리에서 빼먹은 거 찾는 거에서 막혀서 첨에는 deque로 풀려다가 접고 이진트리.. 1707 Maximum XOR With an Element From Array 이번 문제는 Trie 구조를 이용해서 푸는 문제인데, Trie로 푸는 알고리즘 문제는 처음이었고, 그래서 풀 때, 시간이 좀 걸렸었다. 문제는 nums 배열에서 Queries 배열의 각 query의 두 번째 원소보다 같거나 작은 원소들과 첫 번째 원소와 XOR 연산을 했을 때의 최댓값을 찾는 문제이다. 어떠한 수 n과 임의의 수에 대해 XOR연산을 할 때, 만약 임의의 수가 5(101)와 4(100)라면, 공통되는 부분인 10의 계산 결과를 저장할 수만 있다면, 2번 계산하지 않아도 될 것이다. 이 문제에서는 XOR연산의 이러한 점을 이용하여 비트 레벨에서 Trie구조를 만들어 문제를 풀 것이다. 일단 우리가 짤 Trie는 root가 상위 비트, child가 하위 비트인 Trie이다. 그래서 querie.. 이전 1 2 다음
