LeetCode - 페이스북 테크리드 추천 75제

아래 링크를 참고하여 추천하는 75제부터 진행한다. https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU https://qkrrmsdud.tistory.com/9

https://leetcode.com/problems/two-sum/description/ 간단히 풀려면 이중 for문으로 풀 수 있으나 시간복잡도가 O(n^2)이다. 그렇다면 O(n^2)보다 빠르게 해결하기 위해서는 다른 방법이 필요하다. 아이디어1 배열 자체를 오름차순 정렬해서 앞에서부터 탐색하며 합이 맞는 순간 종료한다. --> 배열 자체를 정렬하게...

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ 단순하게 2중 for문으로 푸는 경우 시간초과 발생함. 다른 방법으로 풀어야 한다. Constraints: 1 <= prices.length <= 10^5 0 <= prices[i] <= 10^4 다른 방법이 뭐가 있을...

https://leetcode.com/problems/contains-duplicate/description/ Arrays.sort로 오름차순 정렬하고 앞(적은 인덱스)에서부터 순회하다가 Duplicate인 것을 만나는 순간 종료하는 것은 어떨까? java 8버전 기준 primitive type인 경우 Dual-Pivot QuickSort 쓴다고 알고있...

https://leetcode.com/problems/product-of-array-except-self/description/ 기본 목표는 나눗셈을 하지 않고 O(n)을 달성하는 것이다. 당연히 2중 for문은 불가하다. 나눗셈을 쓰지 말라는 것은 왜일까? nums의 총합을 곱해 total을 찾아놓고, 해당 인덱스 값을 나누면 너무 쉽기 때문인 듯. ...

https://leetcode.com/problems/maximum-subarray/description/ 기본아이디어 처음 인덱스부터 순회하면서 temp sum(누계)을 만들어 두고, 갱신할 max 변수도 설정해둔다. 만약 누계가 current, 즉 nums[i]보다 작다면 왼쪽부터 계산했던 값을 그냥 버린다. 즉, 현재 누계 = nums[i]로 만든...

https://leetcode.com/problems/maximum-product-subarray/description/ 이 문제는 기본적으로 maximum subarray와 같아 보이지만 굉장히 다르다. 곱셈의 특성 때문이다. 음수와 양수의 곱은 음수가 되기 때문에 다음 숫자에 따라 더 커질 수도, 작아질 수도 있기 때문이다. 그래서 단순히 누계가...

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/ 문제에서 제시한 시간복잡도는 O(log n)이다. 정렬된 배열이 n바퀴 돌았다고 가정하는 것이니.. 이분탐색을 해서 찾으라는 건가? 정렬된 배열이 아니라 n바퀴 돈 배열이니 한 번 비튼 문제인 듯 하다. mid를...

https://leetcode.com/problems/search-in-rotated-sorted-array/description/ 이 문제는 Find Minimum in Rotated Sorted Array 문제와 마찬가지로 O(log n) 시간복잡도를 요구한다. 또한 정렬된(rotated 되었지만) 배열을 대상으로 하므로 이분탐색 문제인 것을 알 수...

https://leetcode.com/problems/3sum/description/ Medium 문제기 때문에 당연히 O(n^3)으로는 하지 않는 것을 생각한다. i, j, k가 있을 때 j+k 합산과 i를 더했을 때 0이면 타켓이라고 볼 수 있긴 하다. 그럼 일단 O(n^2)까지는 가능할 것 같다. 맵에 i에 대한 value, index를 세팅해놓고...

https://leetcode.com/problems/container-with-most-water/description/ 일단 미디엄 문제이기 때문에 O(n^2)는 버리는 것으로 생각하고 .. 투포인터를 쓰면 될 것 같다. while로 순회마다 두 포인터 중 하나는 감소하거나 증가할테니 O(N) max 변수를 설정해두고 Math.max로 갈아치워준 ...

https://leetcode.com/problems/sum-of-two-integers/description/ 비트연산자가 익숙하지는 않아 솔루션 참고한다. Carry값을 찾으려면 AND 연산을 하면 되고 XOR 연산을 하면 캐리 고려하지 않고 합계를 계산할 수 있다고 한다. 캐리를 찾았으면 시프트연산해서 자릿수를 올려주고 더이상 캐리가 존재하지 않...

https://leetcode.com/problems/number-of-1-bits/description/ 참고: Integer 클래스에는 bitCount라는 메서드가 존재한다. 솔루션 참고해보니 -1 값과 함께 AND연산해가며 카운트하는 방식이 있고 아니면 int가 32비트라는 점을 참고해서 32번의 shift와 AND연산하며 카운팅하는 방식이 있다....

https://leetcode.com/problems/counting-bits/description/ 문제에서 O(n log n)으로 풀면 쉽지만 O(n) 시간으로 풀 수 있는지 묻고 있다. O(n log n)으로 푸는 방식은 0 ~ n 까지 수행 * 각 순회마다 비트수 계산이다. 비트 수 계산은 Number of 1 Bits 문제에서 사용한 것과 같...

https://leetcode.com/problems/missing-number/description/ O(n) 시간복잡도로 풀라는데, 사실 Binary라고 고정하지 않고 생각하면 쉽다. 그냥 n+1 사이즈로 카피 배열을 만들어서 nums[i]값을 인덱스로 값을 세팅해주면 된다.. boolean이든, 아니면 범위에서 벗어난 int값(예를 들어 -1)을 ...

https://leetcode.com/problems/reverse-bits/description/ int자료형 32비트이므로 32번의 순환 + 시프트연산으로 O(1)으로 해결할 수 있을거란 생각을 했다. 아이디어까지는 좋았으나 마지막비트 누적 연산에서 오류가 있어 통과하지 못하는 케이스가 있었다. 결국 뒤집을 대상(n)의 마지막 비트를 OR 연산하면...

https://leetcode.com/problems/climbing-stairs/description/ DP의 입문이고 많이 본 문제다. 간단하게 풀어본다. 1까지 가는 경우의 수 = 1 (1 step) 2까지 가는 경우의 수 = 2 (1 step + 1 step OR 2 steps) 3부터는 i-1 + i-2가 됨 왜냐? 1 step으로 가는 경우...

https://leetcode.com/problems/coin-change/description/ > 이 문제를 코인 크기대로 정렬한 뒤 큰 순서대로 나누고 나머지 연산으로 누적해간다는 아이디어를 떠올린다면 틀린 것이다. 모르겠으면 아래 경우를 테스트케이스에 추가해 보라. coins = [3, 5], amount = 9 아이디어는 아래와 같다. 우선 ...

https://leetcode.com/problems/longest-increasing-subsequence/description/ 문제에서 O(n log n)으로 풀어보라는 챌린지가 있는데 바로 떠오르진 않고.. O(n^2)는 다음과 같이 할 수 있겠다. nums길이와 똑같은 배열을 만들어서 1로 초기화한다(자기 자신 포함 길이기 때문에 최소 1). ...

https://leetcode.com/problems/longest-common-subsequence/description/ 힌트를 참고해서 2차원 배열로 dp배열을 만들면 된다는 아이디어를 보고.. text1과 text2의 길이를 이용한 dp배열을 만들었다. 이후 2중 for문으로 dpi값을 제어하면 되는데, text1의 i-1 번째와 text2의 j...

https://leetcode.com/problems/word-break/description/ DP왜이렇게 어렵냐.. 고민하다 솔루션 참고 아이디어는 s 길이 + 1만큼의 boolean dp[] 배열을 만들고 해당 인덱스까지(== 문자열에서 해당 포인트까지) 접근 가능한지 여부를 true/false 세팅해둔 뒤 최종적으로 dp[s.length()]하...

https://leetcode.com/problems/combination-sum-iv/description/ Climbing Stairs의 심화버전 같은 문제다. 경우의 수가 nums만큼이 있으므로 이것을 계산해야 한다. dp 배열은 다른 문제들과 같이 target+1 길이를 가지는 int배열로 만들어 주고, dp[target]을 통해 가능한 경우의...

https://leetcode.com/problems/house-robber/description/ 기본적으로 아이디어가 중요하다. 선택지는 2가지가 있다. 현재 인덱스를 터느냐/마느냐다. DP로 풀 때 dp[i]는 i-1 값과 i-2 + (현재인덱스 amount) 중 큰 값으로 넣으면 된다. i-1 값을 그대로 i에 세팅한다는 것은 현재 인덱스(i)...

https://leetcode.com/problems/house-robber-ii/description/ house robber 문제에서 변형이 된 문제다. 집들이 원형으로 이어져 있다는 전제가 추가되었다. 0 ~ n-1 까지 탐색하면 원형 조건에 걸리지 않는다(맨 마지막 집 계산 제외). 1 ~ n 까지 탐색하면 원형 조건에 걸리지 않는다(맨 처음 집...

https://leetcode.com/problems/decode-ways/description/ 숫자는 한자리가 될 수도, 두 자리가 될 수도 있다. 기본적인 아이디어는 dp[i]에 두 자리로 가능한 경우 dp[i - 2]의 값을 누적하고, 한 자리로 가능한 경우 dp[i - 1]의 값을 누적한다. 다만, 중요한 것은 두 경우가 다 가능할 수 있기 ...

https://leetcode.com/problems/unique-paths/description/ 오른쪽과 아래로만 이동 가능하다는 제약이 있다. 그렇다면 i, j 에는 i-1과 j-1값을 더해주면 된다고 생각했다. 방어조건으로는 n이나 m이 1인 경우 무조건 1을 리턴하도록 했다 (한가지 수밖에 없음) dp는 m 사이즈로 세팅해주고, 경우의 수 누...

https://leetcode.com/problems/jump-game/description/ DP는 익숙해지지가 않음.. 핵심 아이디어는 i + nums[i] 가 goal보다 크거나 같으면 닿을 수 있다는 것 goal은 다시 i로 초기화하고 점진적으로 0까지 갈 수 있는지 확인하면 된다. i + nums[i] >= goal 이라면 i까지만 와도 유...

https://leetcode.com/problems/clone-graph/description/ 무방향 그래프 탐색을 하면서 깊은 복사를 하는 문제인 것 같다. Node 인스턴스를 새로 만들어야 한다는 뜻 DFS, BFS 어떤 방식으로든 탐색이 가능할 것 같다. BFS 방식 Queue를 이용해서 poll(), 이어지는 노드는 offer() - 큐가 ...

https://leetcode.com/problems/course-schedule/description/ 아이디어가 떠오르지 않아서 시간초과로 솔루션 참고함 위상 정렬을 통해 유향 그래프에 사이클이 존재하는지 여부를 체크하는 것이 핵심 진입차수를 기록하는 별도의 배열을 만들어서 관리하며 인접리스트를 사용해 선행과 후행의 연결고리를 관리한다. 진입차수...

https://leetcode.com/problems/pacific-atlantic-water-flow/description/ 이런 문제는 재밌어 보인다. 2중 for문 돌면서 특정 r 인덱스에 있는 정점으로부터 출발해 Pacific과 Atlantic에 모두 닿을 수 있는지 체크하면 될 것 같다. 그럼 Pacific에 닿는다는 것과 Atlantic에 ...