인프런 커뮤니티 질문&답변

기존코드

def two_sum(nums, target):
    memo = {}
    for v in nums:
        memo[v] = 1
    for v in nums:
        needed_number = target - v
        if needed_number in memo:
             return True
    return False

기존 코드에서 첫번째 for문은 O(n)이고

두번째 for문은 O(1)이 n번 실행되니까 최종적으로는 O(n)이 되어서 해당 알고리즘의 시간복잡도는 O(n)이되는데

처음에 문제를 설명해주실때의 순서대로라면 4를 먼저넣고 target이 14니까 10이 있는지 확인해보고 없으니까 1을 넣고 13이없는지 확인해보고 없으니까 9를 넣고 5가 없으니까 7을 넣고 7이 없으니까 5를 넣고 9가 있으니까 true를 반환 이라고 생각을 했고 그렇게 로직을 짜면 아래와 같은 코드가 될것같습니다(제가 파이썬을 잘 몰라서 정확한지는 모르겠네요 ㅠㅠ)

def two_sum(nums, target):
    memo = {}
    for v in nums:
        memo[v] = 1
        needed_number = target - v
        if needed_number in memo:
            return True
    return False

해당 코드에서는 첫번째 for문 내부의 시간복잡도가 전부다 O(1)이고 그걸 n번 반복하는것이니 O(n)이라는 최종적인 시간복잡도라고 생각을 하는게 맞을까요??

만약에 아래에 짠 로직이 올바른 로직이라면

위에 로직은 n번 연산하면서 dictionary에 넣고 후에 요소를 돌면서 답을 찾고

아래로직은(코드가 맞다면) dictionary를 다 넣지 않더라도 중간에 값이 나오면 중간에 연산을 끝낼 수 있으니까 조금더 효율적이라고 생각을 했습니다

제가 생각한 방식이 맞는지 그리고 이런 작은(?)효율성이 코딩테스트에서 의미있게 다가올지가 궁금합니다!