배열 nums와 서로 다른 세 정수 a, b, c가 주어졌을 때, 조건을 만족하는 '좋은 삼중항(good triplet)'의 개수를 구해야 합니다.
좋은 삼중항의 조건
삼중항 (nums[i], nums[j], nums[k])이 좋은 삼중항이 되려면 아래 조건들을 모두 만족해야 합니다.
- 0 <= i < j < k < nums의 원소 개수
- |nums[i] - nums[j]| <= a
- |nums[j] - nums[k]| <= b
- |nums[i] - nums[k]| <= c
즉, 인접한 두 원소뿐 아니라 첫 번째와 마지막 원소 사이의 차이까지 주어진 값 이하여야 합니다.
예시
입력이 nums = [5, 2, 3, 3, 12, 9], a = 7, b = 2, c = 3이라면 출력은 4입니다. 좋은 삼중항은 다음과 같습니다.
- (5, 2, 3)
- (5, 2, 3)
- (5, 3, 3)
- (2, 3, 3)
풀이 접근 방법
이 문제는 브루트 포스(완전 탐색) 방식으로 해결할 수 있습니다. 가능한 모든 인덱스 조합 (i, j, k)에 대해 위 조건을 검사하고, 조건을 만족하면 카운트를 증가시키면 됩니다.
구체적인 단계는 다음과 같습니다.
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- i를 0부터 nums 길이 - 1까지 반복합니다.
- j를 i+1부터 nums 길이 - 1까지 반복합니다.
- k를 j+1부터 nums 길이 - 1까지 반복합니다.
- |nums[i] - nums[j]| <= a 이고 |nums[j] - nums[k]| <= b 이고 |nums[i] - nums[k]| <= c 라면 res를 1 증가시킵니다.
- 모든 반복이 끝나면 res를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 더 잘 이해할 수 있습니다.
def solve(nums, a, b, c):
res = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
for k in range(j+1, len(nums)):
if abs(nums[i] - nums[j]) <= a and abs(nums[j] - nums[k]) <= b and abs(nums[i] - nums[k]) <= c:
res += 1
return res
nums = [5, 2, 3, 3, 12, 9]
a = 7
b = 2
c = 3
print(solve(nums, a, b, c))입력
[5,2,3,3,12,9], 7, 2, 3
출력
4
복잡도 분석
이 풀이는 세 겹의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다. 여기서 n은 배열의 길이입니다. 배열의 크기가 작다면 충분히 실용적이지만, 입력 크기가 커지면 슬라이딩 윈도우나 정렬 기반 최적화 기법을 고려해야 합니다. 공간 복잡도는 추가 자료구조 없이 카운터 변수만 사용하므로 O(1)입니다.