[코테 챌린지] 13일차. 수찾기

입력:
1. 첫 줄에 배열의 크기 N이 주어집니다. (1 ≤ N ≤ 100,000)
2. 두 번째 줄에 N개의 정수로 이루어진 배열 A가 주어집니다. 배열의 원소는 중복되지 않습니다.
3. 세 번째 줄에 M이 주어집니다. (1 ≤ M ≤ 100,000)
4. 네 번째 줄에 M개의 정수로 이루어진 배열 B가 주어집니다. 배열의 원소는 중복되지 않습니다.

출력:
- 배열 B의 각 원소가 배열 A에 존재하면 1, 존재하지 않으면 0을 출력합니다.

---

📌 문제 탐색하기 

우리가 문제를 이해해가는 과정을 작성하시면 됩니다.
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 등을 작성해주시면 됩니다.

알고리즘 선택

• 해당 문제는 이분 탐색 또는 해시 집합으로 사용해서 풀 수 있다. 시간 복잡도를 비교해보면.. 
  • 이분 탐색을 사용한 경우 시간 복잡도 : O(N log N + M log N)
  • 해시 집합을 사용한 경우 시간 복잡도 : O(N + M)
• 따라서 이 문제를 풀 때, 해시 집합을 사용하는 것이 더 효율적이라고 생각했다. 

---

📌코드 설계하기 

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡으셨을 것 같습니다.
이제 문제 풀이를 본격적으로 하기 전, 이 문제를 풀기 위한 로드맵을 그려보겠습니다.
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성해주시면 됩니다.
처음에는 어려울 수 있지만, 문제를 풀기 전 미리 지도를 그린다라는 생각으로 적어나가 보시면 좋을 것 같습니다 :)

• 배열 A를 집합(Set)으로 변환합니다.
• 배열 B의 각 원소가 집합 A에 존재하는지 확인합니다.

---

📌 시도 회차 수정 사항 (Optional)

- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

 

x

---

📌정답 코드

n = int(input())
A = set(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))

for b in B:
    if b in A:
        print(1)
    else:
        print(0)