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

* 수업은 JS 기반이지만 Python으로 구현

* 공부하여 수정함

Section 9

reverse

Write a recursive function called reverse which accepts a string and returns a new string in reverse.

// reverse('awesome') // 'emosewa'
// reverse('rithmschool') // 'loohcsmhtir'

# 문자를 입력받아 거꾸로 다시 출력하기
def reverse(str):
    # base case
    # 만약 입력받은 문자열의 길이가 1이라면 문자열을 출력하라
    if len(str) == 1:
        return str
    # different input
    # 입력값 문자열의 두 번째부터 다시 재귀를 하는데, 첫 번째 문자를 제일 끝으로 보낸다.
    # 이를 반복하면 거꾸로 출력을 하게 된다.
    return reverse(str[1:]) + str[0]
    
    
reverse('nohtyP olleH')

isPalindrome

Write a recursive function called isPalindrome which returns true if the string passed to it is a palindrome (reads the same forward and backward). Otherwise it returns false.

// isPalindrome('awesome') // false
// isPalindrome('foobar') // false
// isPalindrome('tacocat') // true
// isPalindrome('amanaplanacanalpanama') // true
// isPalindrome('amanaplanacanalpandemonium') // false

# 문자열을 앞으로 읽으나 뒤로 읽으나 같다면 True를 출력하라
def isPalindrome(str):
    # base case
    # 만약 입력받은 문자열의 길이가 1보다 작다면
    # 문자열 앞으로 읽은 것과 뒤로 읽은 것이 같다는 것
    if len(str) <= 1:
        return True

    # 문자열이 2개 남았을 때 다른 경우 따로 지정해주지 않으면
    # 그 부분을 출력하므로, 따로 지정해둔다.
    # 두 문자를 비교한 값을 출력한다.
    if len(str) == 2:
        return str[0] == str[-1]

    # different input
    # 문자열의 가장 처음과 마지막이 같다면
    # 그 두 문자열을 뺀 나머지를 비교하라
    if str[0] == str[-1]:
        return isPalindrome(str[1:-1])

    # 입력받은 문자열의 길이가 1보다 크고
    # 문자열의 가장 앞과 뒤가 다르다면
    return False
    
isPalindrome('Hello Python')
isPalindrome('amanaplanacanalpanama')
isPalindrome('Hi')

someRecursive

Write a recursive function called someRecursive which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback. Otherwise it returns false.

// const isOdd = val => val % 2 !== 0;
// someRecursive([1,2,3,4], isOdd) // true
// someRecursive([4,6,8,9], isOdd) // true
// someRecursive([4,6,8], isOdd) // false
// someRecursive([4,6,8], val => val > 10); // false

# 주어진 배열 중 한 요소라도 콜백 함수에 True를 반환할 경우 True를 아니라면 False를 반환하라
def someRecursive(arr, callback):
    # base case
    # 더이상 남은 배열 요소가 없다면
    # False를 반환하고 함수를 종료
    if len(arr) == 0:
        return False
    # 만약 callback함수에 배열 첫 번째값이 True 반환하면
    # 전체 함수에 True를 바환
    if callback(arr[0]):
        return True
    # different input
    # 주어진 배열의 두 번째 값부터 다시 확인한다.
    return someRecursive(arr[1:], callback)
    
isOdd = lambda x: x %2 != 0
someRecursive([1,2,3,4], isOdd)
# > True
someRecursive([4,6,8,9], isOdd)
# > True
someRecursive([4,6,8], isOdd)
# > False
someRecursive([4,6,8], lambda x: x > 10)
# > False

flatten

Write a recursive function called flatten which accepts an array of arrays and returns a new array with all values flattened.

// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]
// flatten([[1],[2],[3]]) // [1,2,3]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1,2,3]

중첩 리스트를 해제하여 1차원 리스트로 만드는 과정을 블로그 참고했다.

리스트 마지막 원소를 삽입하는 방법에는 두 가지를 블로그를 참조했다. extend는 반복되는 항목을 넣고, append는 그 자체를 원소로 넣는다.

# 배열 안에 하위 그룹이 있는 경우 모두 해제하여 차원이 하나인 배열로 만들어 반환한다.
def flatten(arr):

    # 재정렬한 배열 변수 선언
    nArr = []

    # 배열의 요소를 하나씩 비교한다.
    for i in arr:
        # different input
        # 만약 요소 값이 리스트라면
        # 그 요소의 내부 값을 다시 재귀적으로 수행한다.
        if type(i) is list:
            # 함수 작동 확인 요소
            print('list', i, nArr)
            nArr.extend(flatten(i))


        # base case
        # 리스트가 아니라면 바로 그 요소를 리스트에 추가하라.
        else:
            # 함수 작동 확인 요소
            print('not list', i, nArr)
            nArr.append(i)

    return nArr
    
flatten([1, [[[3]]], [1]])

 

 

capitalizeFirst

Write a recursive function called capitalizeFirst. Given an array of strings, capitalize the first letter of each string in the array.

// capitalizeFirst(['car','taco','banana']); // ['Car','Taco','Banana']

# 문자로 이루어진 배열을 입력받고, 첫 문자를 대문자로 바꾸어 배열 그대로 출력하라
def capitalizeFirst(arr):
    # base case
    # 만약 배열에 남은 것이 1개일 때 재귀를 멈추고
    # 마지막 문자열의 첫 문자를 대문자로 바꾼다.
    if len(arr) == 1:
        return [arr[0][0].upper() + arr[0][1:]]
    # different input
    # 배열의 첫 번째 문자열의 첫 문자를 대문자로 바꾼것을 배열의 첫 번째 요소로 넣고
    # 다음 요소를 배열의 두 번째 문자열을 재귀적으로 수행한 것을 넣는다.
    return [arr[0][0].upper() + arr[0][1:]] + capitalizeFirst(arr[1:])
    
capitalizeFirst(['car','taco','banana'])

nestedEvenSum

Write a recursive function called nestedEvenSum. Return the sum of all even numbers in an object which may contain nested objects.

nestedEvenSum(obj1); // 6
nestedEvenSum(obj2); // 10

def nestedEvenSum(obj):
    sum = 0
    
    # base case
    # 입력값이 dict가 아니라면, 더이상 분해할 수 없으므로 0을 반환한다.
    if type(obj) != dict:
        return 0

    for key, val in obj.items():
        # 구동 확인 용도
#         print(key, val)
        
        # base case
        # 만약 값이 숫자이면서 짝수라면 sum에 그 값을 더해준다.
        if (type(val) == int) and (val % 2 == 0):
            sum += val
            
        # different input
        # 만약 값이 문자일 경우 그 문자를 key로 한 것을 대상으로 다시 함수를 구동한다.
        else:
            sum += nestedEvenSum(obj[key])


    return sum

obj1 = {
  'outer': 2,
  'obj': {
    'inner': 2,
    'otherObj': {
      'superInner': 2,
      'notANumber': True,
      'alsoNotANumber': "yup"
    }
  }
}

obj2 = {
  'a': 2,
  'b': {'b': 2, 'bb': {'b': 3, 'bb': {'b': 2}}},
  'c': {'c': {'c': 2}, 'cc': 'ball', 'ccc': 5},
  'd': 1,
  'e': {'e': {'e': 2}, 'ee': 'car'}
};
nestedEvenSum(obj1)
# > 6
# nestedEvenSum(obj2)
# > 10

capitalizeWords

Write a recursive function called capitalizeWords. Given an array of words, return a new array containing each word capitalized.

# 문자열로 이루어진 배열을 입력받아, 다 대문자로 이루어진 배열을 반환하라
def capitalizeWords(arr):
    # base case
    # 만약 배열에 남은 것이 1개일 때 재귀를 멈추고 문자를 대문자로 바꾼다.
    if len(arr) == 1:
        return [arr[0].upper()]
    # different input
    # 배열의 첫 번째 문자열을 대문자로 바꾼것을 배열의 첫 번째 요소로 넣고
    # 다음 요소를 배열의 두 번째 문자열을 재귀적으로 수행한 것을 넣는다.
    return [arr[0].upper()] + capitalizeWords(arr[1:])
    
capitalizeWords(['car','taco','banana'])

stringifyNumbers

Write a function called stringifyNumbers which takes in an object and finds all of the values which are numbers and converts them to strings. Recursion would be a great way to solve this!

obj = {
    'num': 1,
    'test': [],
    'data': {
        'val': 4,
        'info': {
            'isRight': True,
            'random': 66
        }
    }
}

def stringifyNumbers(obj):
    
    # basecase
    # 만약 입력값이 dictionary가 아니라면 함수 종료
    if type(obj) != dict:
        return
    
    for key, val in obj.items():
        # 만약 입력값의 value가 숫자라면 문자로 바꿔라
        if type(val) == int:
            obj[key] = str(val)
        # different input
        # 숫자가 아닐경우 그것을 key로 갖는 하위 dictionary가 있다고 가정
        # 그 입력값으로 함수를 불러온다
        else:
            stringifyNumbers(obj[key])
        
    return obj

stringifyNumbers(obj)
# > 
# {'num': '1',
#  'test': [],
#  'data': {'val': '4', 'info': {'isRight': True, 'random': '66'}}}

collectStrings

Write a function called collectStrings which accepts an object and returns an array of all the values in the object that have a typeof string

obj = {
    'stuff': "foo",
    'data': {
        'val': {
            'thing': {
                'info': "bar",
                'moreInfo': {
                    'evenMoreInfo': {
                        'weMadeIt': "baz"
                    }
                }
            }
        }
    }
}
def collectStrings(obj):
    result = []
    
    for key, val in obj.items():
        print(key, val)
        # basecase
        # value 값이 문자일 경우 결과 배열에 추가한다
        if type(val) == str:
            result.append(val)
    
        # different input
        # val이 문자가 아니라 dictionary일 경우 함수를 다시 수행하고
        # 그 결과 배열을 기존 배열에 연장한다.
        else:
            result.extend(collectStrings(obj[key]))
    
    return result

collectStrings(obj)
# > ['foo', 'bar', 'baz']