문제 https://leetcode.com/problems/group-anagrams/description/ Group Anagrams - LeetCode Group Anagrams - Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters e leetcode.com 풀이 난이도: Medium 일단 브루트 포스 방식은 적절해 보이지 않는다...

문제 https://leetcode.com/problems/minimum-window-substring/ Minimum Window Substring - 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 풀이 난이도: Hard 모든 위치에서부터 끝까지 일일이 확인하는 것은 O(N^2)의 복잡도를 가진다. 문자열의 길이가 최대 10,000 이기 때문에 시간 복잡도로 위험해 보인다. 따라서 슬라이딩 윈도우 기법을 적용해보자. left에서 시작해 t를 모두 가지는 rig..

문제 https://leetcode.com/problems/longest-repeating-character-replacement/ Longest Repeating Character Replacement - 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 풀이 난이도: Medium 풀이를 이해하기도 힘들었던 어려운 문제였다. 일단 문자열의 최대길이는 50,000이므로 단순히 전부 시도해보는 것은 무리다. 정답인 위치의 subString을 생각해보자. 해당 subS..

문제 https://leetcode.com/problems/longest-substring-without-repeating-characters/ Longest Substring Without Repeating Characters - 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 풀이 난이도: Medium 일단 본인의 풀이를 소개하고 나서 더 간단한 방법을 설명하겠다. 먼저, 문자열의 각 (idx 번째)문자로 부터 오른쪽으로 이동하여 가장 가까운 같은 문자가 나오..

문제 Word Search - LeetCode Word Search - 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 풀이 난이도: Medium Matirx로 분류되어 있지만, DFS로 해결 가능한 문제였다. 간단히, 문자열의 시작 문자와 동일한 위치에서부터 상하좌우 네 방향을 DFS로 탐색해 나가면 된다. 너무 간단하므로 아래에서는 follow-up 문제까지 고민해보기로 하자. DFS 풀이 코드 좀 더 생각해보기 (pruning) 이번 문제의 follow-up..

문제 https://leetcode.com/problems/rotate-image/ Rotate Image - 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 풀이 난이도: Medium 이것도 일반적으로 푼다면 다음과 같이 순서를 읽어버리면 된다. 하지만 In-place 알고리즘으로 해결해야 하므로, 2차원 배열을 새로 생성하는 과정을 진행하면 안 된다. 이를 위해 어쩔수 없이 2차 for문으로 하나 하나 이동시켜야 한다. 이때 2차원 행렬을 양파의 껍질(shel..

문제 https://leetcode.com/problems/spiral-matrix/ Spiral Matrix - 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 풀이 난이도: Medium 재귀 형식으로 해결한 문제. 행렬을 나선형 순서로 돌아가기 위해서는 결국에는 외각을 한 바퀴 돌고 한 칸 안쪽에서 다시 한 바퀴 도는 것을 반복하게 된다. 따라서 재귀로 표현하기 적합하다. 한 칸의 외각의 범위를 표현하기 위해서는 단 두가지 점인, 왼쪽 위(left top)와 ..

문제 https://leetcode.com/problems/set-matrix-zeroes/ Set Matrix Zeroes - 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 풀이 난이도: Medium 단순히 새로운 2차원 배열에 값을 복사해 넣으면서 만들면 굉장히 쉽지만 O(mn)의 공간 복잡도가 소요된다. 공간 복잡도를 최적화하는 다른 방법으로는 각 row와 column이 0으로 채워져야하는지 여부를 O(n + m) 공간으로 저장은 가능하지만, 문제에서는 i..

문제 https://leetcode.com/problems/merge-k-sorted-lists/ Merge k Sorted Lists - 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 풀이 난이도: Hard 대표적인 우선순위 큐 문제. 일반적인 정렬로 해결하기에는 범위가 너무 크다. 리스트의 최대 개수(k)는 10,000개, 각 리스트의 연결 노드들은 최대 500개가 될 수 있다. 모두 한꺼번에 정렬로 해결할려면 최악의 경우 5,000,000 개의 노드를 정렬..

문제 https://leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - 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 풀이 난이도: Easy 정렬되어 주어지는 2가지 NodeList를 정렬된 순서로 병합하는 문제. 반복문 풀이와 재귀 풀이 두 가지를 모두 확인해보자. 반복문 풀이 반복문은 두 연결 노드의 값을 비교하여 더 작은 값을 새로운 병합 연결 노드와 연결해주자. 최종적으로는 한쪽의..