파이썬으로 정의역과 치역이 함수 관계인지 판별하는 방법

데이터 목록 x(정의역)와 크기가 같은 데이터 목록 y(치역)가 주어졌을 때, x → y가 함수인지 아닌지를 판별해야 합니다. 여기서는 x와 y의 모든 원소가 양수라고 가정합니다.

예를 들어 입력이 x = [1, 3, 2, 6, 5], y = [1, 9, 4, 36, 25]라면 출력은 True입니다. 각 x에 대응하는 y 값이 항상 그 제곱값이므로, 하나의 x에 하나의 y만 대응되는 함수 관계이기 때문입니다.

접근 방법

이 문제는 해시 맵(딕셔너리)을 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 새로운 빈 딕셔너리 mp를 생성합니다.
• x의 모든 인덱스 i에 대해 반복합니다.
  • a := x[i], b := y[i]로 값을 가져옵니다.
  • a가 mp에 없다면 mp[a] = b로 저장합니다.
  • a가 이미 mp에 존재한다면, 같은 정의역 값에 서로 다른 두 개의 치역 값이 대응된다는 의미이므로 False를 반환합니다.
• 반복이 모두 끝나면 충돌이 없었다는 뜻이므로 True를 반환합니다.

구현 예제

아래 파이썬 코드로 위 로직을 구현할 수 있습니다.

def solve(x, y):
    mp = {}
    for i in range(len(x)):
        a = x[i]
        b = y[i]
        if a not in mp:
            mp[a] = b
        else:
            return False
    return True

x = [1,3,2,6,5]
y = [1,9,4,36,25]
print(solve(x, y))

입력

[1,3,2,6,5], [1,9,4,36,25]

출력

True

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 리스트의 각 원소를 한 번씩만 순회하고, 딕셔너리의 삽입 및 조회 연산은 평균적으로 O(1)이기 때문입니다. 공간 복잡도 역시 최악의 경우 모든 원소를 저장해야 하므로 O(n)입니다.