[python]2776_암기왕

사용한 자료구조 및 개념 : set

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

이 문제에서는 두 개의 수열이 주어졌을 때, 두 번째 수열의 각 수가 첫 번째 수열에 존재하는지 여부를 빠르게 확인해야 합니다. 기본적으로 브루트 포스로 모든 요소를 비교할 수도 있겠지만, 그렇게 하면 시간복잡도가 높아져서 효율적이지 못합니다.

효율적으로 해결하기 위해 set 자료구조를 활용했습니다. 파이썬의 set은 내부적으로 해시 테이블을 사용하여, 멤버십 테스트(어떤 요소가 집합에 있는지 확인)를 평균 O(1)의 시간복잡도로 수행합니다. 이를 통해 각 숫자가 첫 번째 수열에 존재하는지를 빠르게 확인할 수 있습니다.

---

🤓 문제 풀이 단계

1️⃣ 입력 받기 및 자료구조 초기화

• 먼저 테스트 케이스(tc)의 수를 입력받습니다.
• 각 테스트 케이스마다 첫 번째 수열의 크기(n1)를 입력받고, 수열을 set으로 변환합니다.
  set으로 변환하면 첫 번째 수열의 숫자들에 대해 빠른 존재 여부 확인이 가능해집니다.

2️⃣ 두 번째 수열 처리

• 두 번째 수열의 크기(n2)를 입력받고, 그 수열을 리스트로 저장합니다.

3️⃣ 존재 여부 검사 및 출력

• 두 번째 수열의 각 숫자에 대해 첫 번째 수열(arr1)에 포함되어 있는지 검사합니다.
• 포함되어 있다면 1을, 아니라면 0을 출력합니다.
• 이 과정은 각 숫자에 대해 set의 멤버십 테스트를 수행하므로 매우 빠르게 처리될 수 있습니다.

---

✅ 세부 구현 포인트 및 이점

• Set 자료구조:
  • 첫 번째 수열을 set으로 변환하여, 각 숫자의 존재 여부를 매우 빠르게 확인할 수 있습니다.
  • 수열의 크기가 큰 경우에도 조회 연산이 평균 O(1)이므로, 효율적인 성능을 보장합니다.

set 자료구조를 사용하여 문제를 풀이하면, 숫자 존재 여부 확인과 같은 작업을 매우 빠르게 수행할 수 있습니다. 특히 큰 데이터 집합에서도 효율적으로 작동하므로, 이와 같은 유형의 문제에 매우 유용합니다.

 

---

Solution Code & 주석

tc = int(input())

for t in range(tc):
    n1 = int(input())
    arr1 = set(map(int, input().split()))
    n2 = int(input())
    arr2 = list(map(int, input().split()))

    for num in arr2:
        if num in arr1:
            print(1)
        else:
            print(0)