for문을 이중으로 사용했기 때문에 시간복잡도가 O(n^2)이다.추가 요구 사항에 이 시간복잡도보다 더 나은 방식은 없는지를 물어보았다.이를 해결한 다른 답변을 가져와봤다.map이라고 써놓으시고, new Map의 사용을 간단하게 표현하신 것 같다.target과 현재 숫
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.매우 쉬운 문제다.입력된
이 문제는 nums1을 변경한다는 것이 주요 포인트이다.아무래도 공간 복잡도를 최소화해서 두 배열을 합치는 방법을 생각해 내라는 것이 목적인 듯 하다.받아온 값을 변경하고자 한다면 splice()를 떠올릴 수 있겠다.또한, nums1 배열은 m+n의 길이를 가지며 m번
필자는 Map 객체를 활용하여 진행했다.가장 많은 개수의 원소를 얻기 위해서는, 각 원소 값이 몇 개가 있는지 알아야하는데바로 생각나는 것이 바로 key, value를 활용하는 것이었다.보통은 일반 객체로 해도 충분하다고 생각되지만,Map 객체가 특정 key를 검색할
in-place 알고리즘을 사용해서 해결하기를 원했기 때문에최대한 변수, 상수를 생성하지 않는 방법으로 해결하고자 했다.splice()는 원본을 변경하기 때문에, 추가적인 공간이 필요하지 않으며,데이터가 삭제되었을 경우, 해당 인덱스로 다음 데이터들이 밀려오기 때문에i
in-place로 해결하기 위해서 추가적인 공간 할당 없이 해결했다.인덱스를 1부터 시작하고, 이전 값과 비교하여 동일한 경우 해당 인덱스를 제거하는 것으로 진행했다.여기서 추가 공간을 쓰지 않기 위해 splice()로 원본을 수정하며 진행했고,제거 연산 후 빈 인덱스
nums 배열을 순회하면서 최대 2번만 중복되도록 하는 문제이다.이 말은 즉, 2개까지는 중복이 허용이 된다는 뜻이다.firstIndex와 lastIndex를 구한 뒤,두 값이 같으면 중복이 아예 없는 것이고, 두 값의 차이가 1이면 같은 값이 2개라는 뜻이므로,이 두
정말 단순하게 생각하고 작성한 코드이다.사실 테스트 케이스는 통과한다.단, 시간 제한에 걸린다는 것 빼고..unshift()를 하면 배열의 원소들이 하나씩 밀리기 때문에 O(n)의 시간이 걸리게 되며,이를 모두 반복한는 것은 상당히 시간을 잡아 먹을 것이다.이 방법은
이중 for문을 돌려서인지 테스트 통과가 거의 끝날 즈음에 시간 초과가 되었다.어떻게 하면 이를 더 간결하게 만들 수 있을까?이중 for문을 벗어나기 위해 고안한 방법이다.기준을 잡고, 그 기준 뒤에 있는 값들 중 가장 큰 값(가장 큰 이익을 내기 위해)을 잡고그 차이
solution 이번 문제는 사실 알고리즘 사고를 적용했다기 보다는, 될 때까지 돌려보면서 예외 처리를 변경해나갔다. 방법은 다음과 같다. 현재 인덱스에서 이동할 수 있는 최대 거리를 구한다. 만약, 그 거리가 마지막 인덱스보다 크다면 그대로 true이다. 여기
고민의 시간에 비해 너무나도 허무하게 해결된 문제이다.정말 수없이 코드를 고쳐봤지만, 간단한 사고로 해결이 되었다.최대의 이익을 얻는 방법은 간단하다.이익이 발생하는 모든 부분에서 이익을 취할 것.즉, 이전 가격보다 올랐으면 그 차이를 이익으로 취하면 된다.그 이익들을
자료 구조인 stack을 구현하는 문제이다.그렇다보니 사실 크게 어려운 것이 없다.아무래도 문제 자체가 알고리즘 지식을 요구하기보다는 자료 구조 자체에 대한 이해를 보는 느낌이라서다른 분들도 답이 비슷했다.다만, 최소값을 구하는 방법이 신기한 분이 계서서 소개를 하고자
이 문제는 two pointer 알고리즘을 사용하는 문제이다.하나의 포인터는 앞에서부터, 다른 포인터는 뒤에서부터 탐색을 진행한다.우선, palindrome임을 확인하기 위해서는 문자와 숫자만 남기고 전부 제거할 필요가 있다.또한, 소문자로 전환하여 끝과 끝을 비교해
가장 간단하게 생각해낼 수 있는 방법이다.이중 for문을 사용해서 target과 일치하는 합을 찾고, 해당 인덱스를 반환하면 된다.이 분은 two pointer 알고리즘을 사용하셨다.맨 앞과 맨 뒤에 포인터를 두고, 그 값들의 합과 target이 일치할 때까지 연산한다
이중 for문에 매 반복마다 slice()와 reduce()까지 있어서 시간 복잡도가 상당하다.그로 인해서 시간 초과가 되었다.반복문을 최대한 줄여봐야겠다.이번에는 slice()를 제거해보았다.그러나 여전히 3중 for문이었고, reduce의 역할이 for문으로 변경되
필자는 sliding window 알고리즘을 사용했다.substring의 최대 길이를 구하는 것이 목적이기 때문에, 사실상 끝까지 연산을 해줘야했다.그러나, 필자의 방법은 start 인덱스를 정하면 그 곳에서부터 만들 수 있는 substring을최대한 만들어낸 뒤에,
문제가 어렵다기보다는 Linked List를 어떻게 사용하는지를 몰라서 많이 헤맸다.head가 배열로 들어오는 줄 알았더니, 전혀 다른 방식의 사용법을 가지고 있었다.문제에서 요구하는 것은 주어진 Linked List에 cycle이 존재하는지 판단하는 것이다.이를 판단
문제는 정말 간단했으나, 조건을 이리저리 생각하다보니 코드가 상당히 길어졌다.풀이는 간단하다.두 개의 Linked List가 있고, 그 둘의 맨 앞부터 합쳐나가면서 새로운 Linked List를 생성한다.이 때, 각 Linked List의 node는 1의 자리 숫자만을
필자는 기준이 될 리스트와 연산을 진행할 리스트를 구분해서 문제를 해결했다.우선 기준 리스트를 linked_list에 이어준 뒤,연산 리스트의 값이 기준 리스트의 값 이상이면서 기준 리스트의 다음 노드 값보다 작으면linked_list에 이어준다.그 후, 기준 리스트의
대표적인 binary search 문제였다.두 개의 포인터를 두고, 그 중앙인 mid를 기준으로target이 mid보다 크면 left를 mid 뒤로 옮겨주고,target이 mid보다 작으면 right를 mid 앞으로 옮겨주면 범위를 좁혀가는 것이다.보통의 경우는 굉장히
이 문제를 보고 두 가지 방법이 생각났다.2차원 배열을 1차원으로 통합하고 binary search를 하는 방법1차원 배열 중 target을 포함하는 범위인지 탐색 후 거기서 binary search를 진행하는 방법필자는 2차원 배열을 1차원으로 통합하는 과정에서 연산
예제로 주어진 3개만 분석을 하고 진행했는데 너무나도 잘못된 접근이었다.주어진 테스트 케이스 3개를 통과하는데만 이정도의 코드가 나왔고,아무리 처음엔 알고리즘 생각하지말고 손수 풀어보라지만,각 케이스에 최적화된 코드를 에러를 마주할 때마다 수정할 뿐이었다.예제 분석에서
이 문제는 문제 자체를 잘 보지 않으면 많이 헤맬 가능성이 높다.같은 값을 가지면서 그 차이가 k보다 같거나 작은 두 인덱스를 얻어야한다.그런데, 주어진 테스트 케이스를 잘 보지 않으면 실수를 할 수 있다.예를 들어 1번 인덱스에 있는 값과 3번 인덱스에 있는 값이 같
magazine에 있는 각각의 문자열이 한번씩만 쓰일 수 있다는 점을 이용하여 문제를 해결했다.문자열을 key로, 사용할 수 있는 횟수를 value로 설정하여 hashMap에 저장하고,ransomNote를 순회하면서, ransomNote의 문자열과 hashMap의 ke
s와 t는 서로의 문자열을 모두 사용하여 재조합할 수 있는 관계이다.따라서, 문자열의 길이가 다르다면 false가 된다.문자열의 길이가 같다면 연산을 시작해볼 수 있겠다.일반적인 hash map 문제와 다를게 없다.우선, 한 쪽 문자열을 hash map으로 만든다.이
solution 1 nums의 모든 값들이 unique하기 때문에 hash map을 만들고, target 값을 찾아 반환하면 된다. 그러나, 문제 분류가 binary search로 되어있었고, 문제 조건에도 O(log N)의 시간 복잡도 내에 해결하기를 바랬기 때문
정렬되지 않은 배열에 대한 binary search는 항상 큰 틀은 같다.조건에 따라 세부 조건이 변경되는 정도인데, 이번 문제도 그런 식으로 해결되었다.주어진 배열 내에서 최소값을 찾는 것이 목표였기 때문에,target을 정해놓고 움직이는 binary search가
solution 이 문제는 배열을 수정하지 않고 peak 값을 찾는 것이 목표이다. 그 외에 어떤 규칙이라도 있으면 좋을텐데, 원소값에 뚜렷하게 보이는 규칙이 없어서 해결하기 어려웠다. 그래서 일단 막무가내로 풀어보기로 했다. 요구되는 시간 복잡도가 O(log N)이
이 문제는 BST의 특성을 직접적으로 사용한다기 보다는,그 특성을 기반으로 새로운 접근을 하는 듯한 느낌이었다.문제에서 요구한 것은 무작위의 두 노드 간 차이 값이 최소인 것을 반환하는 것이었는데,BST는 Tree 구조이므로, 무작위로 두 노드를 설정해서 차이값을 연산
solution
BFS를 활용하여 각 레벨 당 가장 오른쪽의 노드를 얻어내는 문제였다.따라서 기본적인 BFS의 구조에 조건을 부여하여, 같은 레벨에서 마지막 값만 result에 넣어주면 된다.문제를 보고는 가장 오른쪽만 가져오면 되는거 아닐까 할 수도 있는데, 이는 잘못된 생각이다.만
BFS 문제는 Queue를 사용해서 해결한다.따라서, 배열을 활용해서 Queue 구조를 사용했다.여기서 중요한 것은 "같은 레벨"의 노드만 누적합 연산에 사용하는 것이다.그런데, Queue는 계속 변할텐데...?그렇다.그래서 같은 레벨임을 확인하기 위해 연산 시작 전에
search를 제외하고는 일반적인 Trie의 메서드를 구현하는 것이다.search는 일반적인 경우라면 Trie의 최상단부터 children을 확인하면서 내려오면 되는데,이번에는 .이 있는 경우, 어떤 문자열도 될 수 있다는 조건이 붙어있어서 좀 더 깊이 고민해야했다..
Heap 관련 문제라는 것을 보고는 Heapify를 통해 문제를 해결하는 건가 싶었다.그러나, 테스트 케이스를 보면 이게 틀린 방법이라는 것을 알 수 있었다.Heapify를 통해 Max Heap을 만들었지만, 가장 큰 문제는 Heap이 된 상태에서 그를 배열로 표현해도
Min Heap을 사용하는 방법으로 문제를 해결하고자 했다.우선 가능한 상황에 대해서 원소의 합을 구하고, 그 때 사용된 값들을 배열로 만들어 저장한다.Heap에서는 원소의 합을 사용해서 Heapify를 진행하며, 항상 최소값이 root가 되도록 한다.그 후에는 roo
이 문제는 가능한 모든 경로를 탐색하는 DFS를 사용하는 것이 핵심이라고 생각된다.문자열을 다루는 문제였기 때문에 words에 담긴 단어들을 모두 Trie에 생성해주는 과정을 거쳤다.이렇게 생성된 Trie를 board의 알파벳들을 순회하면서 DFS를 진행하면서 생성 가
neighbors의 neighbors의 neighbors...이런 식으로 진행되는, 꼬리의 꼬리를 물고 계속해서 들어가는(혹은 반복하는) 문제이기 때문에Recursion, 그리고 DFS가 떠올랐다.Hash Map을 이용하여 한번 순회한 node를 관리하면서 진행하는 방
이 문제는 여러 가지 장치가 있는 길을 어떻게 하면 가장 빨리 지나가서 목표에 도달할 수 있는지를 구하는 BFS 문제이다.square라고 불리는 각각의 칸들 간에 부모/자식 관계같은 것이 없기 때문에Tree가 아니라 Graph 문제라고 생각된다.(물론 Tree는 Gra
문제에 주어진 조건을 그대로 활용해서 조건문 처리를 해줬다.가장 직관적인 방법이라고 생각된다.Hash Table을 사용하신 분들이 많았다.사실 문제 분류가 Array/String으로 되어있어서 가능한 사용하지 않는 걸로 풀었던건데,역시 빠른게 장땡인 것인가..ㅠㅠ필자와
양 끝의 공백을 지운 뒤, 단어 사이의 공백을 기준으로 문자열을 잘라 words 배열로 만든다.그 후, words 배열의 마지막 원소의 길이를 반환한다.pop()을 사용해서 바로 마지막 문자만 꺼내서 사용하신 분이 계셨다.이 풀이는 메모리마저 훨씬 더 적게 먹기 때문에
haystack의 문자열을 순회하면서, needle 문자열이 처음으로 등장하는 부분의 가장 첫 인덱스를 반환하는 것이 목표이다.count를 사용해서 needle 문자열 충족될 때마다 증가시키면,모든 needle 문자열이 연속으로 나왔을 때 count가 needle.le