problem solving patterns(2)

1. frequency counter pattern

예제 문제1

same([1, 2, 3, 3], [9, 4, 1, 9]) // true
same([1, 2, 3, 3], [9, 4, 1]) // false

 

1. write a function called "same", which accepts 2 arrays.
2. the function should return "ture" if every value in the array has it's corresponding value squared in the second array. 
3. the frequency of values must be the same. 

문제 풀이한 방법

const squared = [1, 9, 25, 25]
getFrequencyOf(squred) // { '1': 1, '9': 1, '25': 2 }

 

1. array1의 모든 값의 제곱인 값을 아이템으로 갖는 새로운 배열 squared을 만든다. 
2. 배열을 인자로 받는 getFrequencyOf 함수를 만든다.
   • 배열의 각 아이템을 key로 하고, 그 아이템의 빈도수를 value로 갖는 객체를 반환하도록 만들었다. 
3. getFrequencyOf(squred)와 getFrequencyOf(array2)가 반환하는 객체 데이터의 값에 key를 이용해 접근(access)해서 값을 비교하였다. 이 때 isSame이라는 배열에 각 값을 비교한 결과를 push 하였다.
4. isSame의 모든 아이템이 true인지 확인한 결과를 same 함수의 결과로 반환하였다. 
5. array2가 squared의 모든 요소를 포함하기만 하면, 그 외의 요소를 가지고 있는지 아닌지는 비교 결과에 영향을 미치지 않는다. 
   • 이 부분은 강의 내용을 통해, length를 비교함으로써 해결할 수 있다는 것을 알았다.  
6. 리팩토링
   • 처음에는 array2가 array1의 모든 값을 포함하고 있는지 비교하는 단계를 거쳤는데, 리팩토링 과정에서 O(n^2)의 time complexity를 가지고 있는데다가, 필요하지도 않은 로직이라는 사실을 알아차리고 삭제했다.
7. 결론 | O(n)의 시간 복잡도를 갖는 same 함수를 작성했다. 근데 너무 오래 걸린 것 같다. 한 3시간...? ㅋㅋㅋㅋ
8. 느낀점, 보완할 점  
   • 강의 듣기 전에 혼자 문제를 풀어보는 과정이 재미있었고, 내가 문제를 푼 방식이랑 보편적인 해결 방식이랑 거의 유사하다는 것을 알게 되었을 때 뿌듯했다. 
   • 좀 더 빠르게 문제를 해결하는 방법은 없을지
   • problem solving 단계를 잘 지키면서 문제를 풀어보려고 했는지(아ㄴㅣ요) 
   • 새로운 배열이나 객체를 변수에 저장할 때 space complexity에 대해 전혀 생각하지 않은 점? 가독성을 고려하면 변수에 값을 저장하는 것이 더 낫지 않을까, 생각이 든다. 

예제 문제2

• given 2 strings, write a function to determine if the second string is an anagram of the first.

문제 풀이한 방법

2. multiple pointers pattern

예제 문제1

1. write a function called sumZero which accepts a sorted array of integers. 
2. the function should find the first pair where the sum is 0.
3. return an array that includes both values that sum to zero or undefined if a pair doesn't exist.

sumZero([-3, -2, -1, 0, 1, 2, 3]) // [-3, 3]
sumZero([-2, 0, 1, 3]) // undefined

문제 풀이한 방법

1. 배열을 오름차순으로 sort 한다.
2. 주어진 배열에 0이 있다면, 0을 제외한 아이템으로만 이뤄진 새로운 배열을 만든다.
   • sumZero([0, 0, 1, 5])를[0, 0]으로 처리할 것인지, false로 처리할 것인지에 대한 언급은 문제에 없음
   • 일단은 내 마음대로 0이 있으면 제외하는 거로 함
3. 배열의 아이템을 순서대로 iterate 하면서, 합을 0으로 만드는 pair 아이템이 존재하는지 확인한다.
4. pair가 존재하면 배열을, 아니면 undefined을 반환한다.
5. 리팩토링 
   • n^2 보다 낮은 time complexity를 갖는 로직을 어떻게 작성해야 할지 감이 안와서 early return을 최대한 많이 이용했다(사실 그러면서도 이게 뭔 소용인가 싶었다....). 
   • 양수, 음수끼리 배열을 나눈 뒤에 사이즈가 더 작은 숫자 집합을 기준으로 반복문을 실행했다. 
   • 반복문 안에서도 전체 배열이 아니라 양수 또는 음수 배열에서  search(includes 메서드)를 실행했다. 
6. 결론 | n^2의 time complexity를 갖는 sumZero 함수를 만들었다. 어떻게 더 효율적으로 코드를 작성할 수 있을지 고민해 봤는데, 방안이 잘 떠오르지 않았다. 
7. 느낀점, 보완할 점 
   • ??? 가독성을 높이려다 보니까 자꾸 변수를 많이 쓰게 되는데 이대로 괜찮은 걸까...
   • 그래도 가장 큰 값이랑 작은 값으로 뭔가를 할 수도 있겠다는 생각을 계속 했었던 것에 위로를 느낌

예제 문제2

1. implement a funtion called countUniqueValues, which accepts a sorted array. 
2. the function counts the unique values in array.
3. there can be negative numbers in the array, but it will always be sorted. 

countUniqueValues([1, 2, 2, 5]) // 1, 2, 5 => 3
countUniqueValues([-2, -1, -1, 0, 2]) // 2, -1, 0, 2=> 4
countUniqueValues([]) // 0

문제 풀이한 방법

1. 다중 포인터를 사용하지 않아도 문제를 풀 수 있는 방법이 많았다(set을 이용한 방법, frequency counter 패턴). 그래도 굳이 포인터를 이용해서 문제를 풀어 보았다. 
2. pointer1과 pointer2를 재할당 가능한 변수로 만든다.
3. uniqueValues라는 변수에 배열을 저장하고, pointer1이 가리키는 값을 push 한다.
4. pointer1은 배열의 첫번째 아이템을 가리키고, 2는 첫번째 아이템과 다른 값을 가진 바로 다음 아이템을 가리킨다.
5. pointer 2가 가리키는 아이템이 존재하면 uniqueValues 배열에 push 한다.
6. pointer1이 2를 가리키고, 2는 다시 pointer 1과 다른 값을 갖는 바로 다음 아이템을 가리킨다.
   • 이 때 findIndex를 메서드를 이용했는데, findIndex가 조건에 맞는 가장 첫번째 아이템을 반환한다는 사실을 간과해서 시간을 잡아먹었다. 
7. pointer2가 배열의 마지막 index를 가리킬 때 까지 3~4를 반복한다.
8. array의 length가 0이거나 1인 경우에는 pointer를 사용하지 않고 바로 값을 return 한다.
9. 리팩토링
   • 강의 힌트를 보고 findIndex를 사용하지 않고 문제를 푸는 방법으로 리팩토링했다. 
   • 강의 힌트를 보고222 uniqueValues라는 변수를 만들지 않고도 문제를 푸는 방법을 사용했는데, 이게 굉장히 흥미롭고 재미있었다. 강의에서는 배열 안의 데이터를 변경했지만, uniqueValues가 몇 개인지만 알아내도 상관없는 문제였기 때문에 나는 배열 안의 데이터를 변경하지 않고 문제를 풀었다. 
10. 결론
    • n의 time complexity를 갖는 함수를 만들었다.
    • frequency counter 패턴과 set의 경우에도 n의 복잡도를 갖기 때문에, 어떤 방법을 이용해도 좋을 것 같다.

3. sliding window pattern

예제 문제1

1. write a function called maxSubarraySum which accepts an array of integers and a number called n. 
2. the function should calculate the maximum sum of n consecutive elements in the array. 

maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2) // 10
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4) // 17
maxSubarraySum([], 3) // null

문제 풀이 방법

1. 배열의 길이보다 n이 크면 null을 return 한다.
2. subsum과 max라는 변수를 만든다.
3. i = 0부터 시작해서 n개의 아이템의 합계를 subsum에 저장한다.
4. 그 값이 max보다 크면, max에 subsum을 할당한다. +) subsum을 0으로 초기화한다.
5. i가 lastIndex를 가리킬 때 까지 4번을 반복한다.
6. max를 반환한다.
7. 결론 
   • n^2의 time complexity를 갖는 함수를 작성했다. 
   • 강의를 듣기 전에 혼자 문제를 풀어보는 과정이 재미있긴 한데, n^2 해결 방안만 생각나서 아쉽다. 그래도 강의 들어보면 해결책에 내가 생각했던 방법들이 조금씩 들어있어서, 그런 걸 확인해 보는 것도 재미있게 느껴진다. 

4. divide & conquer pattern

This pattern involves dividing a data set into smaller chunks and then repeating a process with a subset of data. 
This pattern can tremendously decrease time complexity. 

 

=> quick sort, merge sort와 같은 정렬 알고리즘에서 사용하는 패턴이 여기에 포함된다. 

예제 문제

1. given a sorted array of integers, write a function called search, that accepts a value and returns the index where the value is located.
2. if the value is not found, returns -1.  

search([1, 2, 3, 4, 5], 2) // index 1

문제 풀이 방법

1. Linear search | 배열 전체를 순회하면서 찾고자 하는 value와 같은 값을 갖는 아이템의 index를 반환한다. O(N)의 시간 복잡도를 갖는다.
2. Binary search | 찾고자 하는 value가 정렬된 배열의 중간값보다 큰 값인지 확인한다. 큰 값이라면 배열의 오른쪽, 작은 값이라면 왼쪽에서 찾고자 하는 값을 검색한다. 찾고자 하는 값을 반환할 때 까지 이 과정을 여러 번 반복할 수 있다.