숫자로 구성된 리스트 nums가 주어졌을 때, 세 개의 수 a, b, c가 존재하여 a² + b² = c² 관계를 만족하는지 확인하는 문제입니다. 즉, 리스트 안에 피타고라스 삼중항(Pythagorean triple)이 포함되어 있는지 판별해야 합니다.
예를 들어, 입력이 [10, 2, 8, 5, 6]이라면 출력은 True가 됩니다. 그 이유는 8² + 6² = 64 + 36 = 100 = 10²이 성립하기 때문입니다.
해결 접근 방법
이 문제는 정렬과 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 리스트의 모든 숫자를 제곱한 뒤, 내림차순으로 정렬한 임시 리스트 tmp를 생성합니다.
- tmp의 각 인덱스 i와 해당 값 n에 대해 다음을 반복합니다.
- base := n (현재 확인 중인 빗변 후보)
- left := i + 1, right := len(tmp) - 1 로 설정합니다.
- left <= right인 동안 아래 과정을 반복합니다.
- t := tmp[left] + tmp[right] (두 수의 합 계산)
- t == base이면 True를 반환합니다.
- t > base이면 합을 줄여야 하므로 left를 1 증가시킵니다.
- 그 외의 경우 합을 키워야 하므로 right를 1 감소시킵니다.
- 모든 탐색이 끝날 때까지 조건을 만족하는 조합이 없으면 False를 반환합니다.
내림차순으로 정렬했기 때문에 tmp[left]가 tmp[right]보다 크거나 같습니다. 따라서 합이 base보다 크면 왼쪽 포인터를 앞으로 이동해 값을 줄이고, 합이 base보다 작으면 오른쪽 포인터를 뒤로 이동해 값을 키우는 방식으로 탐색 범위를 좁혀 나갑니다. 이 방법의 시간 복잡도는 O(n²)입니다.
예제 코드
class Solution:
def solve(self, nums):
tmp = sorted([n*n for n in nums], reverse=True)
for i, n in enumerate(tmp):
base = n
left = i + 1; right = len(tmp) - 1
while left <= right:
t = tmp[left] + tmp[right]
if t == base:
return True
elif t > base:
left += 1
else:
right -= 1
return False
ob = Solution()
print(ob.solve([10, 2, 8, 5, 6]))
입력
[10, 2, 8, 5, 6]
출력
True