nums라는 숫자 리스트가 주어졌다고 가정해 봅시다. 이때 우리가 구해야 할 것은, 자기 자신보다 1 큰 값(x + 1)도 같은 리스트 안에 함께 존재하는 요소 x의 개수입니다.
예를 들어 입력이 [2, 3, 3, 4, 8]이라면 출력은 3이 됩니다. 그 이유는 2(→3 존재), 3(→4 존재), 그리고 또 하나의 3(→4 존재)까지 총 3개의 요소가 조건을 만족하기 때문입니다. 반면 8은 9가 리스트에 없으므로 포함되지 않습니다.
해결 접근 방법
이 문제는 집합(set)을 활용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- s := nums에 있는 요소들을 삽입하여 집합(set)을 생성합니다.
- count := 0 으로 초기화합니다.
- nums의 각 요소 i에 대해 다음을 수행합니다.
- 만약 i + 1이 집합 s에 존재한다면, count를 1 증가시킵니다.
- 최종적으로 count를 반환합니다.
집합을 사용하는 이유는 특정 값의 존재 여부를 확인할 때 평균적으로 O(1)의 시간 복잡도를 가지기 때문입니다. 덕분에 전체 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 효율적으로 동작합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution: def solve(self, nums): s = set(nums) count = 0 for i in nums: if i+1 in s: count += 1 return count ob = Solution() nums = [2, 3, 3, 4, 8] print(ob.solve(nums))
입력
[2, 3, 3, 4, 8]
출력
3
위 코드에서는 먼저 리스트를 집합으로 변환하여 빠른 조회를 가능하게 만든 뒤, 원본 리스트를 순회하면서 각 요소의 다음 값(i + 1)이 집합에 있는지 확인합니다. 중복된 요소도 각각 독립적으로 카운트되므로, 위 예시에서 3이 두 번 등장하면 두 번 모두 계산됩니다.