Description

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

Input

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

Output

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

Solution

• 1차 풀이: Dictionary 사용

  n = input()
  n_data = set(map(int, input().split()))
  m = input()
  m_data = list(map(int, input().split()))
  m_dict = {x:1 if (x in n_data) else 0 for x in m_data}
  
  for k in list(m_dict):
      print(m_dict[k])

  틀렸습니다 출력

  • 반례: m_data에 중복된 key값이 입력될 경우

    5
    1 3 4 7 5
    5
    1 1 3 9 7
    {1: 1, 3: 1, 9: 0, 7: 1}
    1
    1
    0
    1

• 2차 풀이: 딕셔너리를 리스트로 바꾸니 해결되었다.

  n = input()
  n_data = set(map(int, input().split()))
  m = input()
  m_data = list(map(int, input().split()))
  m_list = [1 if (x in n_data) else 0 for x in m_data]
  
  for k in m_list:
      print(k)

• 조금 더 간결하게 아래와 같이 쓸 수 있다.

  n, n_data, m = input(), set(map(int, input().split())), input()
  m_data = list(map(int, input().split()))
  
  for k in m_data:
      print(1 if k in n_data else 0)

Feedback

# 다른 사람 풀이 1

import sys
input = sys.stdin.readline

def BOJ_1920():
    n,A,m = input(),set(input().split()),input()
    res=""
    for i in input().split():
        res += "1\n" if i in A else "0\n"
    print(res)

BOJ_1920()

1. 문제명을 함수로 정의해서 푸는 것도 멋진 것 같다.
2. sys.stdin.readline > raw_input() > input() 순으로 빠르다.
   → 대량의 데이터를 반복적으로 입력받을 때 input() 대신 sys.stdin.readline()을 이용하면 성능이 향상된다.

# 다른 사람 풀이 2

n = int(input())
array = set(map(int, input().split()))
m = int(input())
x = list(map(int, input().split()))

for i in x:
    if i not in array:
        print('0')
    else:
        print('1')

Source

• 백준 1920
• 입력 속도 비교