자료구조와 알고리즘 문제(feat. return, unreachable code)

문제 : 배열에서 특정요소 찾기

input = [3, 5, 6, 1, 2, 4]

내가 짠 코드

def exist(number, array):
    for i in array:
        if number in array:
            return True
        else:
            return False
            
result = exist(2, input)
print(result) // True

def exist(number, array):
    for i in array:
        if number == i:
            return True
        else:
            return False
            
result = exist(2, input)
print(result) // False

정답

def exist(number, array):
    for i in array:
        if number == i:
            return True

    return False
    
result = exist(2, input)
print(result) // True

운이 좋다면 한번만에 값을 찾을 수도 있지만,
최악의 경우 배열의 길이만큼 연산을 해야 값을 찾을 수 있다

→ 빅오 표기법으로 표시하면 $O(N)$,
빅 오메가 표기법으로 표시하면 $Ω(1)$ 의 시간복잡도를 가진 알고리즘

알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석한다.
대부분의 입력값이 최선의 경우일 가능성은 굉장히 적으며,
항상 최악의 경우를 대비해야 하기 때문이다.

문제 : 배열요소를 모두 곱한 값 vs 모두 더한 값 비교

input = [0, 3, 5, 6, 1, 2, 4]

첫번째 시도

def compare(array):
    def plus(array):
        x = 0
        for i in array:
            x += i
        return x

    def multiply(array):
        y = 1
        for i in array:
            y = y*i
        return y

    return  max(plus, multiply) // error

result = compare(input)
print(result)

TypeError: '>' not supported between instances of 'function' and 'function'

max함수의 매개변수에 함수는 못넣어서 실패

두번째 시도

def compare(array):
    x = 0
    for i in array:
        x += i
    return x

    y = 1
    for i in array:
        y = y*i
    return y

    if x > y:
        return x
    elif y > x:
        return y
    else:
        return print('같다')

result = compare(input)
print(result)

값은 나오긴 했으나 억지로 짜낸 더러운 코드로 이용가치 0

세번째 시도

def compare(array):
    x = 0
    for i in array:
        x += i
    return x

    y = 1
    for i in array:
        y = y*i
    return y

    print(max(x, y))

compare(input)

위의 if문 대신 max로 정리를 시도했는데 결과값이 안나와서 디버깅을 해 보니 return x에서 구문이 끝나버리고 결과적으로 x값만 계속 도출이 되었다. 뒤에 식이 이어지는데 왜..?

그러다 전구모양을 클릭하고 발견한 것

unreachable code....?

unreachable code = 도달할 수 없는 코드
어떠한 경우에도 절대 실행되지 않는 코드

출처 : https://runebook.dev/ko/docs/javascript/errors/stmt_after_return

🚫return문이 실행되면 메소드는 그 즉시 종료된다

고친 코드

def compare(array):
    x = 0
    for i in array:
        x += i

    y = 1
    for i in array:
        y = y*i

    return max(x, y)

print(compare(input))

잘 된다 🎊

정답코드

def find_max_plus_or_multiply(array):
    multiply_sum = 0
    for number in array:
        if number <= 1 or multiply_sum <= 1:
            multiply_sum += number
        else:
            multiply_sum *= number
    return multiply_sum


result = find_max_plus_or_multiply

print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))