LeetCode - 릿코드 에이스 코딩 인터뷰 75제

LeetCode추천 에이스 코딩 인터뷰 75제를 진행한다.https://leetcode.com/studyplan/leetcode-75/

https://leetcode.com/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75 인덱스 두개로 이어나가면 쉽다. 이것도 충분히 답이 되지만 StringBuilder 대신 char array를 사용해서 시간을 더 줄이는 방법도 있음

https://leetcode.com/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75 str1과 str2를 정순, 역순으로 합쳤을 때 같지 않으면 substring의 대상이 아님을 알 수 있다. 어떻게 해도 common diviso...

https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/description/?envType=study-plan-v2&envId=leetcode-75 cnadies중 max값을 찾아놓고 그것보다 큰지 작은지만 알아보면 된다.

https://leetcode.com/problems/can-place-flowers/description/?envType=study-plan-v2&envId=leetcode-75 그냥 단순하게 앞뒤만 봐주면 될듯 꽃을 놓을 수 있는 경우 index + 1도 의미가 없기 때문에 i++도 같이 해줌

https://leetcode.com/problems/reverse-vowels-of-a-string/description/?envType=study-plan-v2&envId=leetcode-75 나는 스택에 쌓아놓고 역순으로 뺐다. 다른 풀이법으로는 left, right 두 가지 포인터로 양쪽 끝부터 탐색하면서 둘 다 모음인 경우 둘이 바꾸는 방법이 ...

https://leetcode.com/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=leetcode-75 Java는 split 정규식으로 되기 때문에 "\\s+"로 split하면 사이의 공백이 몇개든 상관없이 나눌 수 있다. 그럼 배열 역순으로 공백 추가해주면서 S...

https://velog.io/@potato_song/LeetCode-Product-of-Array-Except-Self-Array-Medium 해당 시리즈와 중복이므로 링크만 넣고 끝냄

https://leetcode.com/problems/increasing-triplet-subsequence/description/?envType=study-plan-v2&envId=leetcode-75 핵심은 순회하면서 가장 작은 값(a)이면 갱신 중간 값(b)이면 갱신 현재 수가 1,2를 모두 불만족 (현재 숫자는 3번째로 큰 수)

https://leetcode.com/problems/string-compression/description/?envType=study-plan-v2&envId=leetcode-75 추가 공간을 사용하면 안되고 원본 배열을 활용해야 한다. 순회하면서 start character와 같은것이 찾아지는 만큼 count++, i++ 해 주고, 별도의 new i...

https://leetcode.com/problems/move-zeroes/description/?envType=study-plan-v2&envId=leetcode-75 2중 for문을 활용하면 너무 쉬운 문제다. O(N)으로 푸는 방법을 생각해봐야 한다. 문제 카테고리가 투포인터이므로 포인터 두개를 활용할 수 있는 방법으로 해야 한다. 0이 아닌 것을...

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=leetcode-75 투포인터로 t를 순회하면서 매치되는 글자가 있는 경우 sIndex를++한다. 최종적으로 sIndex == s.length()면 매치되는 순서대로 탐색을 완료했다는 뜻이므로 정답 조건...

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75 중복이므로 링크만 단다. https://velog.io/@potato_song/LeetCode-Container-With-Most-Water-Array-Mediu...

https://leetcode.com/problems/max-number-of-k-sum-pairs/solutions/4367159/o-n-2-o-nlogn-o-n-meme-checkpoint/?envType=study-plan-v2&envId=leetcode-75

https://leetcode.com/problems/maximum-average-subarray-i/description/?envType=study-plan-v2&envId=leetcode-75 O(N^2) 시간복잡도로 풀면 타임리밋에 걸린다. 아래처럼 미리 합을 구해놓고, 윈도우를 옮겨가면서 계산해야 한다 O(N)

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/?envType=study-plan-v2&envId=leetcode-75 슬라이딩 윈도우니 시간복잡도는 O(N)을 목표로 한다. 기본적으로 첫 합계를 계산해두고 윈도우를 이동하면서...

https://leetcode.com/problems/max-consecutive-ones-iii/description/?envType=study-plan-v2&envId=leetcode-75 이전의 다른 문제들과 달리 단순히 윈도우만 이동시켜서 되는 문제는 아니다. 0을 k수만큼 flip할 수 있기 때문에 이것을 기준으로 봐야 함. 순회하면서, rig...

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/description/?envType=study-plan-v2&envId=leetcode-75 힌트 참고했다. 0이 항상 한 개 껴있다고 생각하라고 한다. 그럼 아이디어가 잘 나왔다. 첫 번째 순회에서 0이 한 ...

https://leetcode.com/problems/find-the-highest-altitude/description/?envType=study-plan-v2&envId=leetcode-75 아주 쉬운 구간합 문제 따로 설명은 필요 없을 것 같다.

https://leetcode.com/problems/find-pivot-index/description/?envType=study-plan-v2&envId=leetcode-75 처음엔 아래같이 left 누계배열, right 누계배열 해서 풀었는데 사실 leftSum, rightSum 만 있으면 되므로 배열이 전혀 필요없다. 뭔생각을하고 풀었을까? 수정...

https://leetcode.com/problems/find-the-difference-of-two-arrays/description/?envType=study-plan-v2&envId=leetcode-75 딱히 설명 필요 없을 듯

https://leetcode.com/problems/unique-number-of-occurrences/description/?envType=study-plan-v2&envId=leetcode-75 설명은 딱히 필요없을 것 같다. 다만 HashSet 생성자에 map.values 넣는 비용보다 순회하면서 바로 중복 찾아내서 리턴시키는 비용이 대부분의 경...

https://leetcode.com/problems/determine-if-two-strings-are-close/description/?envType=study-plan-v2&envId=leetcode-75 문제풀이의 핵심은 각 두 연산에 집착하지 말고, 논리적으로 보는 것 스왑을 무제한으로 할 수 있기 때문에 사실상 글자의 빈도수가 일치하는지만 보면...

https://leetcode.com/problems/equal-row-and-column-pairs/description/?envType=study-plan-v2&envId=leetcode-75 해시 문제이므로 정석적으로 푼다면 1번 풀이처럼 풀어야 할 것 같았다. 행 -> 열 순서 순회 결과와 열 -> 행 순서 순회 결과를 해시맵에 담아두고 같은 키...

https://leetcode.com/problems/removing-stars-from-a-string/description/?envType=study-plan-v2&envId=leetcode-75 스택을 사용하거나, 아니면 index-1을 통해 값을 비교하거나 선택할 수 있을 것 같다. 스택 문제니까 정석적으로 스택을 사용했다. 참고로 StringB...

https://leetcode.com/problems/asteroid-collision/description/?envType=study-plan-v2&envId=leetcode-75 소행성 방향이 다른 경우에만 체크해주는게 좋다. 루프를 돌면서 아래 방식으로 제거할 소행성을 체크한다. 방향이 다른 동안(while), 현재 소행성이 stack.peek()...

https://leetcode.com/problems/decode-string/description/?envType=study-plan-v2&envId=leetcode-75 인풋이 제대로 되어있다고 가정하므로 고민할 것은 많이 줄었다. 일단 다른 문제와 마찬가지로 stack문제기 때문에 되도록이면 stack 자료구조를 쓴다. 인코딩된 body는 '['가...

https://leetcode.com/problems/number-of-recent-calls/?envType=study-plan-v2&envId=leetcode-75 ping의 입력값은 오름차순이기 때문에 정렬에 대한 고민은 필요없음 그 외에 특별한 점은 없다.

https://leetcode.com/problems/dota2-senate/description/?envType=study-plan-v2&envId=leetcode-75 처음에 문제를 잘못 이해했었다. 중요한건 순서대로 권리 행사가 가능하다는 것이며 라운드마다 권리를 잃은 senate는 제외된다는 것이다. 그렇다는 것은 두 값이 다를 때 인덱스가 낮...

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/?envType=study-plan-v2&envId=leetcode-75 나는 한 번 순회해서 n을 구하고, n /2 값을 구한 다음 next를 바꿔줄 노드를 선택하도록 했다. 찾은 노드의 next = next...

https://leetcode.com/problems/odd-even-linked-list/description/?envType=study-plan-v2&envId=leetcode-75 odd/even 두 개의 포인터를 두고 while 순회하면서 서로 next 포인터를 바꿔주면 된다. 짝수가 뒤로 붙기 때문에 while 조건은 (even != null ...

https://leetcode.com/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=leetcode-75 현재 노드의 next와 prev를 바꿔주는 것이 핵심 최종적으로 뒤집힌 포인터를 바라보게 되므로 prev를 리턴해야 역순 탐색이 가능해 정답처리된다.

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/description/?envType=study-plan-v2&envId=leetcode-75 i번째는 (n-i-1)번째와 짝이므로 왼쪽 끝과 오른쪽 끝에서부터 투포인터 탐색으로 볼 수 있다. 그러나 단방향으로 연결된 Linked List라...

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75 간단한 DFS 문제다. 재귀로 풀기 위해 메서드를 따로 뺐고, depth 누계를 가지고 다니도록 했다. 탈출조건은 node == null로 했고, 탐색은 ...

https://leetcode.com/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75 left 우선 탐색, 후에 right 탐색하는 방식으로 재귀든 스택이든 순회를 하면 되고 각각 얻어진 결과를 가변길이 자료구조에 넣어두면 될 것 같다 (얼마나 큰지 모르니까 ...

https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75 Good node를 찾기 위해서는 dfs 탐색과정에 현재까지의 max값을 가지고 다녀야 한다. max는 순회 시마다 Math.max(max, next...

https://leetcode.com/problems/path-sum-iii/description/?envType=study-plan-v2&envId=leetcode-75 이전 문제와 비슷한 것 같지만, 단순히 max만 구할 게 아니라 누계 sum을 구해야 한다. 처음에는 List 형태로 가지고 다니면서 재귀 전에 넣고 재귀 후에 빼는 것을 생각해 봤으...

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75 방향에 대한 인자를 받아서 역방향으로 dfs 순회하면 지그재그는 쉽게 찾을 수 있다. 그러나 문제 이해를 잘 못해서 same direction...

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75 탈출조건은 current가 null이거나, p거나, q일 때 left와 right 탐색 시 모두 존재하면 - current node가 ...

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=leetcode-75 BFS, 큐 사용해서 순회하되 각 레벨의 마지막 원소만 result List에 add하면 될 것 같다. 즉 while문이 한 번 돌 때마다 que에서 가장 ...

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75 레벨 별 합계를 구해서, 레벨 별 합계가 가장 높은 레벨을 리턴하는 문제다. 다만 합계가 같은 경우 낮은 레벨이 우선한다. Map을 써서 `` ...

https://leetcode.com/problems/search-in-a-binary-search-tree/description/?envType=study-plan-v2&envId=leetcode-75 이진 탐색 트리는 왼쪽이 작고 오른쪽이 크다. val을 기준으로 오른쪽으로 갈 지, 왼쪽으로 갈 지 판단하면 되겠다. 계속 순회하면서 root.val =...

https://leetcode.com/problems/delete-node-in-a-bst/description/?envType=study-plan-v2&envId=leetcode-75 처음에 while 사용해서 풀어보려 했는데 장황해졌다. 재귀적으로 접근하는게 코드 가독성이 좋다고 판단함 핵심은 지울 노드가 자식을 어떻게 가지고 있느냐에 따라 달라짐 ...

https://leetcode.com/problems/keys-and-rooms/description/?envType=study-plan-v2&envId=leetcode-75 DFS 문제인데, 뻗어나갈 수 있는 조건이 rooms.get(current)안에 들어있다고 보면 되겠다. 일단 모든 방을 갔는지 체크하는 boolean[] visited를 만들어 ...

https://leetcode.com/problems/number-of-provinces/description/?envType=study-plan-v2&envId=leetcode-75 문제를 보면 딱 떠오르는 아이디어는, input 배열을 순회하면서 만나는 모든 노드에 체크해주는 것 첫 순회 시 이어지는 모든 노드에 대해 visited 체크를 하고 나면...

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/?envType=study-plan-v2&envId=leetcode-75 두 방향을 모두 담는 인접 리스트로 구현할 수 있다. int[] {이웃 번호, 방향} 연결 리스트로 이어진 ...

https://leetcode.com/problems/evaluate-division/description/?envType=study-plan-v2&envId=leetcode-75 작성중

https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/description/?envType=study-plan-v2&envId=leetcode-75 처음에는 그냥 단순하게 BFS로 풀었다. visited로 중복은 최소화했고, 큐에 넣을 때마다 step 증가시켜서 최소 스텝을 리턴할 수 있게 했...

https://leetcode.com/problems/rotting-oranges/description/?envType=study-plan-v2&envId=leetcode-75 이 문제는 BFS로 풀 때, 첫 큐에 들어갈 원소가 여러개다. 썩은 오렌지가 여러 곳에 있을 수 있기 때문 따라서 썩은 오렌지 순회용 2중 for문을 돌며 큐에 넣는다. 이후에...

https://leetcode.com/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=leetcode-75 소팅하지 않고 풀어야 한다. Quickselect 알고리즘이나 우선순위 큐 사용해야 할 듯 PriorityQueue 사용해서 풀어본다. 아이디어는 오...

https://leetcode.com/problems/smallest-number-in-infinite-set/description/?envType=study-plan-v2&envId=leetcode-75 문제가 특이하다. 일단 모든 양의 정수를 담아둘 수 있는 곳은 없기 때문에, 당연히 내부적으로는 특정 변수의 증감으로 표현해야 함 (next) 생성자...

https://leetcode.com/problems/maximum-subsequence-score/description/?envType=study-plan-v2&envId=leetcode-75 처음에 감이 안와서 힌트봄 힌트에 nums2를 기준으로 정렬하면 좋겠다고 써있다. 그럼 nums1과 nums2 인덱스를 쌍으로 엮은 pair를 만들어 num2 ...

https://leetcode.com/problems/total-cost-to-hire-k-workers/description/?envType=study-plan-v2&envId=leetcode-75 left, right 두 개의 우선순위 큐를 사용하면서 두개의 포인터를 사용할 수 있겠다. left는 costs의 왼쪽부터, right는 costs의 오른쪽...

https://leetcode.com/problems/guess-number-higher-or-lower/description/?envType=study-plan-v2&envId=leetcode-75 이분탐색을 구현하는 가장 심플한 문제로 보인다. 항상 start, end, mid를 기억하자. 다만 mid값을 구할 때는 start + (end - sta...

https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/?envType=study-plan-v2&envId=leetcode-75 O(n^2) 방식으로 풀면 엄청나게 느리겠지만 할 수는 있겠다. 그러나 이분탐색 카테고리로 분류된 만큼 O(n log n)으로 풀어야 하겠...

https://leetcode.com/problems/find-peak-element/description/?envType=study-plan-v2&envId=leetcode-75 마찬가지로 이분탐색 문제고 문제 자체에서 O(log n)시간복잡도를 제시한다. 엄격하게 큰 원소를 찾아야 하는데, 배열 밖에 있는 것보다는 항상 크다고 가정한다고 한다. 가...

https://leetcode.com/problems/koko-eating-bananas/description/?envType=study-plan-v2&envId=leetcode-75 k를 구하는 이분 탐색인 것 같다. 따라서 mid값이 바뀔 때마다 바나나를 전부 먹을 수 있는지 체크하는 로직이 있어야 함 다만 문제는 start가 몇이고 end가 몇인가...

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=leetcode-75 처음에는 BFS로 풀었다. "" 부터 시작해서 큐에 넣고, 큐 사이즈만큼 순회하면서 다음 큐에는 que.poll() + 다음 문자를 넣어주는...

https://leetcode.com/problems/combination-sum-iii/description/?envType=study-plan-v2&envId=leetcode-75 일단 k가 n보다 크면 정답이 절대로 될 수 없으므로 바로 리턴 backtrack은 재귀적으로 수행하는데, List형태의 콤비네이션을 계속 가지고 다녀야 할 듯. 답이 ...

https://leetcode.com/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&envId=leetcode-75 흔히 보는 피보나치 수열 문제하고 동일한 논리다. 하나 늘었다고 해서 다를 건 없다. bottom-up 또는 top-down DP로 풀 수 있겠다. bottom-up...

https://leetcode.com/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&envId=leetcode-75 돌다리 건너기인가.. 비슷한 문제를 본 것 같은데 DP 초급에 많이 등장하는 유형인 듯 메모이제이션 사용해서 바로 풀어봤다. 중요한 부분은 한 칸 또는 두 칸을 ...

https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=leetcode-75 중복이다. 다른 시리즈에서 풀었다. https://velog.io/@potato_song/DP-Medium-House-Robber 요약 초기화: dp[0] = nums[0]: 첫번째 집 터는 경우 ...

https://leetcode.com/problems/domino-and-tromino-tiling/description/?envType=study-plan-v2&envId=leetcode-75 이건 못풀겠어서 답을 봤다. https://leetcode.com/problems/domino-and-tromino-tiling/solutions/116581/d...

https://leetcode.com/problems/unique-paths/?envType=study-plan-v2&envId=leetcode-75 다른 시리즈에서 이미 풀었던 문제다. https://velog.io/@potato_song/DP-Medium-Unique-Paths 요약 dpi = 1으로 첫 열 모두 1로 초기화 dp0 = 1으로 첫 행...

https://leetcode.com/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=leetcode-75 다른 시리즈에서 이미 풀었던 문제다. https://velog.io/@potato_song/DP-Medium-Longest-Common-Subsequence ...

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/?envType=study-plan-v2&envId=leetcode-75 산 경우와 판 경우의 max를 계속 누적해가면 되겠다. 수수료는 사거나 팔 때 한 번만 내면 된다고 했으니 일관...

https://leetcode.com/problems/edit-distance/?envType=study-plan-v2&envId=leetcode-75 2차원 dp 배열을 사용한다. word1의 i번째와 word2의 j번째 수행 결과는 dpi + 1에 들어갈 것이므로 dp배열의 크기는 word1.length() + 1 + 1]로 해준다. dp배열 초기화...

https://leetcode.com/problems/counting-bits/?envType=study-plan-v2&envId=leetcode-75 다른 시리즈에서 풀었던 문제다. https://velog.io/@potato_song/Binary-Easy-Counting-Bits

https://leetcode.com/problems/single-number/?envType=study-plan-v2&envId=leetcode-75 XOR 연산을 활용한다. a ^ a = 0 이고, a ^ 0 = a 이므로 모든 값을 XOR 하면 짝수로 등장한

https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/?envType=study-plan-v2&envId=leetcode-75 못풀겠어서 솔루션 참고 int이므로 32번의 순회 중 조건에 맞는 경

https://leetcode.com/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=leetcode-75 Trie 자료구조를 표현할 클래스가 별도로 필요하다. Node라는 이름의 노드를 만든다. 노

https://leetcode.com/problems/search-suggestions-system/description/?envType=study-plan-v2&envId=leetcode-75 Trie 자료구조를 만들어서 풀어본다. 다만 문제 특성 상 완전히 일치하

https://leetcode.com/problems/non-overlapping-intervals/description/?envType=study-plan-v2&envId=leetcode-75 일단 intervals[i] = [start i, end i] 이므로 겹

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=leetcode-75 이전문제와 유사하게 end 기준 정렬한 뒤

https://leetcode.com/problems/daily-temperatures/description/?envType=study-plan-v2&envId=leetcode-75 단조스택 문제. 각 순회마다 해야하는 것 스택의 peek()보다 현재 온도가 높으면,

https://leetcode.com/problems/online-stock-span/description/?envType=study-plan-v2&envId=leetcode-75 처음에 stack을 이용해서 peek()값이 현재 값보다 작거나 같은 동안 pop하도록