숫자 리스트 nums가 주어졌을 때, 리스트 안에 서로 3배 관계에 있는 두 숫자가 존재하는지 확인하는 문제입니다. 즉, 어떤 숫자가 다른 숫자의 정확히 3배인 경우가 있는지 검사해야 합니다.
예를 들어 입력이 nums = [2, 3, 10, 7, 9]라면 결과는 True입니다. 리스트 안의 9가 3의 3배이기 때문입니다.
해결 접근 방법
이 문제는 정렬과 두 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
포인터 i를 0으로 초기화합니다.
리스트 n을 오름차순으로 정렬합니다.
포인터 j를 1로 초기화합니다.
j가 리스트의 길이보다 작은 동안 아래 과정을 반복합니다.
3 * n[i]가 n[j]와 같다면 True를 반환합니다.
3 * n[i]가 n[j]보다 크다면 j를 1 증가시킵니다.
그 외의 경우에는 i를 1 증가시킵니다.
반복문이 종료되면 조건을 만족하는 쌍이 없다는 뜻이므로 False를 반환합니다.
리스트를 먼저 정렬한 뒤 두 포인터를 이동시키며 값을 비교하기 때문에, 전체 시간 복잡도는 정렬 비용을 포함해 O(n log n)입니다. 이해를 돕기 위해 실제 구현 예제를 살펴보겠습니다.
예제 코드
class Solution:
def solve(self, n):
i = 0
n.sort()
j = 1
while (j < len(n)):
if (3*n[i] == n[j]):
return True
if (3*n[i] > n[j]):
j += 1
else:
i += 1
return False
ob = Solution()
print(ob.solve([2, 3, 10, 7, 9]))
입력
[2, 3, 10, 7, 9]
출력
True