문제 설명
서로 다른 n개의 정수로 이루어진 배열 nums와, 공통 원소가 없는 두 개의 집합 A와 B가 주어졌다고 가정해 봅시다. 행복도(happiness) 변수는 처음에 0으로 초기화되며, 배열 nums의 각 정수 i를 하나씩 살펴봅니다. 만약 i가 집합 A에 속한다면 행복도를 1만큼 증가시키고, i가 집합 B에 속한다면 행복도를 1만큼 감소시킵니다. 모든 원소를 확인한 후 최종 행복도 값을 구하는 것이 목표입니다.
예를 들어 입력이 nums = [1,2,5,8,6,3], A = {5,8,9,7,3}, B = {2,4,12,15}라고 한다면 결과는 2가 됩니다. 그 이유는 5, 8, 3이 집합 A에 포함되어 행복도가 3이 되었지만, 2가 집합 B에 포함되어 1을 차감해 최종적으로 2가 되기 때문입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 행복도(happiness)를 0으로 초기화합니다.
- nums의 각 원소 i에 대해 반복합니다.
- i가 집합 A에 속하면 행복도를 1 증가시킵니다.
- 그렇지 않고 i가 집합 B에 속하면 행복도를 1 감소시킵니다.
- 최종 행복도 값을 반환합니다.
구현 코드
아래 예제 코드를 통해 더 쉽게 이해할 수 있습니다.
def solve(nums, A, B):
happiness = 0
for i in nums:
if i in A:
happiness += 1
elif i in B:
happiness -= 1
return happiness
nums = [1,2,5,8,6,3]
A = {5,8,9,7,3}
B = {2,4,12,15}
print(solve(nums, A, B))
입력
[1,2,5,8,6,3], {5,8,9,7,3}, {2,4,12,15}
출력
2
시간 복잡도
파이썬에서 set(집합)은 해시 테이블 기반으로 구현되어 있기 때문에 특정 원소의 포함 여부를 확인하는 연산은 평균적으로 O(1)의 시간이 걸립니다. 따라서 배열 nums의 길이를 n이라 할 때 전체 알고리즘의 시간 복잡도는 O(n)입니다. 만약 리스트(list)를 사용했다면 포함 여부 확인에 O(n)이 걸려 전체 복잡도가 O(n²)까지 늘어날 수 있으므로, 빠른 조회가 필요한 경우에는 반드시 집합(set)을 사용하는 것이 좋습니다.