백준 10815 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

오랜만에 다시 문제를 접하니 처음에 그냥 생각 없이 풀었다.

 

코드부터 보자.

 

코드

array = []

array2 = []

n = int(input())

array = list(map(int,input().split()))

m= int(input())

array2 = list(map(int,input().split()))

   

for k in array2 :

    if k in array :

        print('1',end=' ')

    else:

        print('0',end=' ')

시간초과다.

 

 

입력값을 보니 500000이 될 수 있다.

 

위 코드의 경우 최악의 시간이 500000^2만번으로 예상된다.

 

따라서 해쉬테이블을 만들어 사용했다.

 

해쉬테이블은 충돌이 없을 경우 시간복잡도 O(1)을 가진 아주 효율적인 방법이다.

 

또한 충돌하여도 O(n)의 시간복잡도를 가진다.

 

하지만 전제조건에  "두 숫자 카드에 같은 수가 적혀있는 경우는 없다."라고 주어져 있기에, 충돌은 일어나지 않는다.

 

정답 코드

 

코드

array = []

array2 = []

n = int(input())

array = list(map(int,input().split()))

dict={i:i for i in array}

m= int(input())

array2 = list(map(int,input().split()))

   

for k in array2 :

    if k in dict :

        print('1',end=' ')

    else:

        print('0',end=' ')

배운 점

1. 해쉬테이블은 충돌이 발생할 수 있는데, 오픈 방식과 클로즈 방식을 통해 해결할 수 있다.

2. 해쉬테이블은 시간 복잡도는 해소할 수 있지만, 공간복잡도에서는 불리한 모습을 보여준다.