5주차 실력진단

이번에는 DP 문제까지 풀고 탈락했다.
사실 DP 도 Knapsack 문제는 어려워 하는데, 이 문제가 아니라 풀 수 있었다ㅋㅋ

다음 문제는 순열 문제 인것 같아서 엥 그냥 풀면 되는거 아냐? 하고 풀었다가 계속 시간초과에 걸렸다.

HashMap

시간초과에 걸리지 않기 위해 HashMap 을 사용해 풀어보자
문제: https://www.codetree.ai/missions/8/problems/sum-of-two-num?&utm_source=clipboard&utm_medium=text

count = {}
for elem in nums:
    diff = k - elem
    if diff in count:
        ans += count[diff]
    
    if elem in count:
        count[elem] += 1
    else:
        count[elem] = 1
    
    # print(count, ans)
print(ans)

핵심은 k 에서 보기에 있는 수를 하나씩 빼서 차이 값이 배열에 있는 값인지 확인하는 것이다. 그리고 같은 위치에 있는 경우의 수를 중복 계산하지 않게 count 라는 빈 dict 을 활용하자.

풀이 방법 자체는 너무 간단한데 이 아이디어를 떠올리지는 못했다 ㅠㅠ
그리고 풀이 방법을 알았을 때, 완전 유레카...