[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 6

Section 6

Frequency Counter - sameFrequency

Frequency Counter - sameFrequency
Write a function called sameFrequency. Given two positive integers, find out if the two numbers have the same frequency of digits
Your solution MUST have the following complexities:Time: O(N)

Sample Input:
sameFrequency(182,281) // true
sameFrequency(34,14) // false
sameFrequency(3589578, 5879385) // true
sameFrequency(22,222) // false

# 두 입력값의 숫자들의 구성이 상호간에 똑같은가
def sameFrequency(num1, num2):
    # 숫자를 문자로 변환
    num1 = str(num1)
    num2 = str(num2)

    # 만약 두 숫자의 자릿수가 다르다면 return False
    if len(num1) != len(num2):
        return False

    # 두 숫자의 요소 개수를 셀 딕셔너리 선언
    num1Cnt = {}
    num2Cnt = {}

    # 만약 num1Cnt key에 이미 있는 요소라면, 그 value를 하나 더하고
    # 아니라면 num1Cnt에 새로운 key를 생성하고 그 value는 1로 둔다
    for i in num1:
        if i in num1Cnt:
            num1Cnt[i] += 1
        else:
            num1Cnt[i] = 1

    # 위코드를 num2에 똑같이 적용
    for i in num2:
        if i in num2Cnt:
            num2Cnt[i] += 1
        else:
            num2Cnt[i] = 1
    # 제대로 저장되었는지 확인하는 용도
    # print(num1Cnt, num2Cnt)

    
    for i in num1Cnt:
        # 만약 num1에 있는 요소가 num2에 없다면 return False
        if i not in num2Cnt:
            return False
        # num2 요소별 개수와 num1 요소별 개수가 동일하지 않으면 return False
        if num2Cnt[i] != num1Cnt[i]:
            return False
    # 모든 것을 만족하면 True
    return True
    
sameFrequency(14223, 43212)
sameFrequency(14223, 4312)

Frequency Counter / Multiple Pointers - areThereDuplicates

Implement a function called, areThereDuplicates which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in.  You can solve this using the frequency counter pattern OR the multiple pointers pattern.

Examples:
areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true
areThereDuplicates('a', 'b', 'c', 'a') // true

Restrictions:
Time - O(n)
Space - O(n)

Bonus:
Time - O(n log n)
Space - O(1)

# 중복 요소가 존재하는지 확인하는 함수
# areThereDuplicates ver Frequency Counter 
def areThereDuplicates(*arg):
# 여러 개 인수를 받을 때는 *를 이용하면 된다

    # 입력된 요소 개수를 셀 딕셔너리 선언
    Cnt = {}

    for i in arg:

        # 숫자를 문자로 변환
        i = str(i)

        # 만약 Cnt에 이미 있는 요소라면 value에 1을 더하라
        if i in Cnt:
            Cnt[i] += 1
        # 만약 Cnt에 없는 요소라면 key를 새로 생성하고 value를 1로 선언하라
        else:
            Cnt[i] = 1

    # 만약 Cnt의 value가 1이상인 것이 있다면 return True
    for i in Cnt:
        if Cnt[i] > 1:
            return True

    # 조건을 만족하지 못한다면 return False
    return False
    
areThereDuplicates('asdf', 'asd', 21, '21')
areThereDuplicates('asdf', 'asd', 21, 'asdf')

# 중복 요소가 존재하는지 확인하는 함수
# areThereDuplicates ver Multiple Pointers
def areThereDuplicates(*arg):
# 여러 개 인수를 받을 때는 *를 이용하면 된다

    # 입력된 요소를 정렬할 리스트 선언
    args = []

    for i in arg:
        # 주어진 입력값을 리스트에 입력하기
        args.append(i)
    # 입력값 배열을 정렬
    args.sort()

    # 포인터 2개를 선언
    start = 0
    next = 1

# while 루프문
    # next 포인터가 배열의 끝 위치일 때까지 루프를 돌린다
    while(next < len(args)):
        # 만약 start와 next 위치의 배열 값이 동일할 경우 return True
        if args[start] == args[next]:
            return True
        start += 1
        next += 1
    # 조건을 만족하지 못한다면 return False
    return False
    
areThereDuplicates('aaa', 'asdf', 'fds', 'aaa')
areThereDuplicates('aasa', 'asdf', 'fds', 'aaa')
areThereDuplicates(1, 3, 5, 11, 2)

Multiple Pointers - averagePair

Multiple Pointers - averagePair Write a function called averagePair. Given a sorted array of integers and a target average, determine if there is a pair of values in the array where the average of the pair equals the target average. There may be more than one pair that matches the average target.

Bonus Constraints:
Time: O(N)
Space: O(1)

Sample Input:
averagePair([1,2,3],2.5) // true
averagePair([1,3,3,5,6,7,10,12,19],8) // true
averagePair([-1,0,3,4,5,6], 4.1) //
false averagePair([],4) // false

# 주어진 정렬된 배열에서 주어진 값을 평균으로 하는 짝이 있는지 확인하는 함수
def averagePair(arr, num):
    
    # 포인터 2개를 선언
    start = 0
    end = len(arr) - 1

    # start 포인터가 end 포인터보다 작은 경우 while 루프를 돌린다
    while(start < end):
        # 요소 짝의 평균을 선언
        avg = (arr[start] + arr[end]) / 2
        
        # 만약 함수의 주어진 값 num과 요소 짝의 평균이 같다면 return True
        if num == avg:
            return True
        # 만약 함수의 주어진 값 num이 요소 짝의 평균보다 크다면, start 포인터를 오른쪽으로 한 칸 이동
        elif num > avg:
            start += 1
        # 만약 함수의 주어진 값 num이 요소 짝의 평균보다 작다면, end 포인터를 왼쪽으로 한 칸 이동
        else:
            end -= 1
    # 조건을 만족하지 못했다면 return False
    return False


averagePair([1, 2, 3, 4, 5], 3.55)
averagePair([1, 2, 3, 4, 5], 3.5)
averagePair([1, 2, 3, 4, 5], 3)

Multiple Pointers - isSubsequence

Write a function called isSubsequence which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string. In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing.

Examples:
isSubsequence('hello', 'hello world'); // true
isSubsequence('sing', 'sting'); // true
isSubsequence('abc', 'abracadabra'); // true
isSubsequence('abc', 'acb'); // false (order matters)

Your solution MUST have AT LEAST the following complexities:
Time Complexity - O(N + M)
Space Complexity - O(1)

# 첫번째 문자열이 두번째 문자열에 속하는지 확인하는 함수
def isSubsequence(str1, str2):
    
    # 포인터 2개 선언
    P1 = 0
    P2 = 0

    # 포인터2가 긴 문자열의 길이 보다 짧은 동안만 while 루프 돌리기
    while(P2 < len(str2)):
        # 만약 str2의 P2번째 문자와 str1의 P1번째 문자가 같다면 P1 값을 하나 올린다
        # 다음 순서 문자의 비교 준비
        if str2[P2] == str1[P1]:
            P1 += 1
        # 만약 짧은 문자열의 길이와 P1의 값이 같아졌다면
        # P1이 P2에 있다는 것이므로 return True
        if P1 == len(str1):
            return True
        # 루프를 하나 돌 때마다 P2의 값을 하나 올린다
        # 짧은 문자열과 같아도, 같지 않아도 긴 문자열의 다음 문자와 비교해야함
        P2 += 1
    
    # 조건에 만족하지 않았다면 return False
    return False
    
    
isSubsequence('Hi', 'Hello, Hi')
isSubsequence('Sup', 'Hello, Hi')

# 첫번째 문자열이 두번째 문자열에 속하는지 확인하는 함수
# ver O(1) 공간이 아닌 재귀
def isSubsequence(str1, str2):
    
    # 만약 입력받은 짧은 문자열의 길이가 0이라면
    # 긴 문자열과의 비교에서 모두 같았다는 의미이므로
    # return True
    if len(str1) == 0:
        return True

    # 만약 짧은 문자열의 길이가 0이 아닌데,
    # 입력받은 긴 문자열의 길이가 0이라면
    # 짧은 문자열과의 비교할 것이 더이상 없으므로
    # return False
    elif len(str2) == 0:
        return False

    # 긴 문자열의 첫 번째 문자와 짧은 문자열의 첫 번째 문자를 비교하여
    # 둘이 같다면, 재귀적으로 다시 불러오는데, 이때 입력값을
    # 짧은 문자열과 긴 문자열 모두 다음 값을 비교해야 하므로 2번째 값부터 나머지까지로 둔다.
    if str2[0] == str1[0]:
        return isSubsequence(str1[1:], str2[1:])

    # 긴 문자열의 첫 번째 문자와 짧은 문자열의 첫 번째 문자를 비교하여
    # 둘이 같지다면, 재귀적으로 다시 불러오는데, 이때 입력값을
    # 짧은 문자열은 그대로, 긴 문자열은 2번째 값부터 나머지까지로 둔다.
    return isSubsequence(str1, str2[1:])
    
isSubsequence('Sup', 'Hello, Hi')
isSubsequence('Hi', 'Hello, Hi')

Sliding Window - maxSubarraySum

Given an array of integers and a number, write a function called maxSubarraySum, which finds the maximum sum of a subarray with the length of the number passed to the function.
Note that a subarray must consist of consecutive elements from the original array. In the first example below, [100, 200, 300] is a subarray of the original array, but [100, 300] is not.

maxSubarraySum([100,200,300,400], 2) // 700
maxSubarraySum([1,4,2,10,23,3,1,0,20], 4) // 39
maxSubarraySum([-3,4,0,-2,6,-1], 2) // 5
maxSubarraySum([3,-2,7,-4,1,-1,4,-2,1],2) // 5
maxSubarraySum([2,3], 3) // null

Constraints:
Time Complexity - O(N)
Space Complexity - O(1)

# 주어진 배열에서 주어진 숫자만큼의 이어진 하위 집합의 합 중 가장 큰 것은 무엇인가?
def maxSubarraySum(arr, num):
    
    if len(arr) < num:
        return 'Undefined'

    # maxsum을 배열의 첫 번째부터 주어진 숫자번째 까지의 합으로 선언
    maxsum = sum(arr[:num])
    # 임시합은 최대합으로 선언
    tmpsum = maxsum

    # tmpsum을, 기존의 값에서 첫 번째 하위 배열(0번째부터 num-1번째 까지)의 첫 번째 요소를 빼고,
    # 그 다음 하위 배열(1번째~nmum까지 에서 앞뒤로 위치값을 1씩 더한다.)의 마지막 요소를 더한다
    # 원래의 하위 배열 합과 그 다음 하위 배열 합 중 더 큰 것을 maxsum에 선언
    for i in range(num, len(arr)):
        tmpsum = tmpsum - arr[i - num] + arr[i]
        maxsum = max(maxsum, tmpsum)
    
    # return 계산된 maxsum
    return maxsum
    
maxSubarraySum([1, 2, -2, 3, 4, 1, 5], 3)
maxSubarraySum([1, 2], 3)

Sliding Window - minSubArrayLen

Write a function called minSubArrayLen which accepts two parameters - an array of positive integers and a positive integer.
This function should return the minimal length of a contiguous subarray of which the sum is greater than or equal to the integer passed to the function. If there isn't one, return 0 instead.
Examples:
minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

Time Complexity - O(n)
Space Complexity - O(1)

# 주어진 숫자와 같거나 커다란 연결된 하위 집합 중 가장 짧은 것은 무엇인가?
def minSubArrayLen(arr, num):
    
    # 만약 배열 전체 합이 주어진 숫자보다 적다면 return 0
    if sum(arr) < num:
        return 0

    # 포인터 전자를 0, 후자를 1 이라고 둔다.
    former = 0
    later = 1

    # 하위 배열의 합
    Sum = 0
    # 하위 배열의 길이
    mincnt = float('inf')
    # 임시 배열 길이
    tmpcnt = 0

    # 후자 포인터의 위치가 배열의 길이보다 작을 때까지 루프를 돌린다.
    while(former < len(arr)):
        # 제대로 작동하는지 확인하는 용도
        print(former, later, mincnt, tmpcnt, Sum)
        # 배열에서 전자와 후자 위치까지의 합을 tmpsum에 배정
        Sum = sum(arr[former:later])
        tmpcnt = later - former

        # 만약 배열 합이 주어진 숫자보다 작고,
        # 포인터 후자가 배열 길이보다 작다면
        # 포인터 후자를 하나 늘려라.
        if (Sum < num) and (later < len(arr)):
            later += 1

        # 만약 배열 합이 주어진 숫자보다 크다면
        # 하위 배열 길이와 임시 배열 길이 중 더 작은 것을 하위 배열 길이에 배정하라 
        # 포인터 전자를 하나 늘려라.
        elif (num < Sum):
            mincnt = min(mincnt, tmpcnt)
            former += 1

        # 그 어느것에도 속하지 않는다면 while을 나와라
        else:
            break

    # 만약 mincnt가 무한값이라면, return 0
    if mincnt == float('inf'):
            return 0

    # mincnt가 무한이 아니라면 그 값을 return
    return mincnt
    
minSubArrayLen([3, 2, 0, 9, -4, 2, 8, 7], 10)
minSubArrayLen([3, 2, 0, 9, -4, 2, 8, 7], 20)

Sliding Window - findLongestSubstring

Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring('longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

Time Complexity - O(n)

# 입력한 문자중에 문자의 중복이 없는 가장 긴 하위 문자열의 길이를 출력하라
def findLongestSubstring(str):

    # 만약 문자열이 비어있다면 return 0
    if len(str) == 0:
        return 0

    # 포인터 전자와 후자 선언
    former = 0
    later = 1

    # 문자열에서 적어도 1개는 있으니 cnt는 1로 선언
    # tmp도 cnt와 같다고 선언
    cnt = 1
    tmp = cnt

    # 포인터 후자가 문자열의 길이보다 작을 때까지 루프를 돌린다
    while(later < len(str)):

        # 제대로 돌아가는지 확인용
        print(former, later, tmp, cnt)

        # 문자열에서 포인터 전자 위치의 값과 후자 위치의 값이 동일하지 않으면
        # tmp의 값을 1씩 더해준다.
        # 하위그룹 문자열 갯수가 늘어나는 것과 같다.
        if str[former] != str[later]:
            tmp += 1

        # 만약 문자열에서 포인터 전자 위치의 값과 후자 위치의 값이 동일하거나
        # 후자의 위치가 문자열의 길이 - 1의 위치라면 = 문자의 끝자리라 더이상 비교할 것이 없다는 얘기
        # cnt와 tmp 중 더 큰 것을 비교해 cnt에 넣어두고,
        # tmp는 1로 초기화하고 전자 포인터에 1을 더해주어 다음 문자열부터 하위 그룹을 생성한다.
        if (str[former] == str[later]) or (later == len(str) - 1):
            cnt = max(cnt, tmp)
            tmp = 1
            former += 1

        # 후자 포인터를 하나씩 더해주어 다음 문자열을 비교한다.
        later += 1

    # return 가장 긴 하위 그룹 문자열 갯수
    return cnt
    
findLongestSubstring('asdf')
findLongestSubstring('asdfaasdfjkwadsf')