파이썬에서 한 요소만 수정해 두 배열을 동일하게 만들 수 있는지 확인하는 방법

두 개의 배열 nums1, nums2와 정수 값 k가 주어졌다고 가정해 봅시다. 이때 nums1의 요소 중 단 하나만 다음과 같은 방식으로 수정해 두 배열을 동일하게 만들 수 있는지 확인해야 합니다.

수정 방식은 nums1의 임의의 요소에 [-k, k] 범위 안의 값을 더하는 것이며, 이 작업은 딱 한 번만 수행할 수 있습니다.

예제 입력 살펴보기

입력이 다음과 같다고 해봅시다.

nums1 = [5, 7, 11]
nums2 = [5, 5, 11]
k = 8

이 경우 출력은 True입니다. nums1[1]인 7에 범위 [-8, 8] 안에 있는 값 -2를 더하면 5가 되어 nums2와 완전히 동일한 배열을 만들 수 있기 때문입니다.

문제 해결 접근 방법

이 문제는 다음 절차를 따라 해결할 수 있습니다.

nums1과 nums2 두 리스트를 각각 오름차순으로 정렬합니다.
임시 플래그 변수 temp를 False로 초기화합니다.
다른 위치를 기록할 변수 idx를 -1로 초기화합니다.
i를 0부터 nums1의 길이 - 1까지 반복하며 다음을 검사합니다.
- nums1[i]와 nums2[i]가 서로 다른 경우:
  - temp가 이미 True라면, 두 번째 차이점이 발견된 것이므로 즉시 False를 반환합니다.
  - 그렇지 않으면 temp를 True로 설정하고, idx에 현재 인덱스 i를 저장합니다.
반복이 끝난 후, idx가 -1(두 배열이 이미 동일함)이거나 |nums1[idx] - nums2[idx]| <= k를 만족하면 True를 반환합니다.
그 외의 경우에는 False를 반환합니다.

핵심 아이디어는 정렬 후 요소별로 비교했을 때 서로 다른 위치가 최대 하나여야 하며, 그 위치의 값 차이가 k 이하일 때만 조건을 만족한다는 점입니다.

구현 코드

아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

def solve(nums1, nums2, k):
    nums1.sort()
    nums2.sort()

    temp = False

    idx = -1
    for i in range(len(nums1)):
        if nums1[i] != nums2[i]:
            if temp:
                return False
            temp = True
            idx = i

    if idx == -1 or abs(nums1[idx] - nums2[idx]) <= k:
        return True
    return False

nums1 = [5, 7, 11]
nums2 = [5, 5, 11]
k = 8
print(solve(nums1, nums2, k))

입력

[5,7,11], [5,5,11], 8

출력

True

시간 복잡도 분석

이 풀이의 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)입니다. 여기서 n은 배열의 길이입니다. 정렬 없이 해시 맵 등을 활용해 빈도를 비교하는 방법도 가능하지만, 위 방식은 구현이 간단하고 직관적이라 실전에서 널리 사용됩니다.