[백준 10815] 파이썬 : 숫자 카드

10815

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

[정답1]

import sys
N = int(sys.stdin.readline())
a_list = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
b_list = list(map(int, sys.stdin.readline().split()))
a_list = set(a_list)
for b in b_list:
    if b in a_list:
        print('1', end = ' ')
    else:
        print('0', end = ' ')
print()

.

.

.

[정답2]

import sys
N = int(sys.stdin.readline())
a_list = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
b_list = list(map(int, sys.stdin.readline().split()))
a_list.sort()
def bin(x, y, s, e):
    if s > e:
        return 0
    mid = (s+e)//2
    if x == y[mid]:
        return 1
    elif x < y[mid]:
        e = mid - 1
    elif x > y[mid]:
        s = mid + 1
    return bin(x, y, s, e)
 
for b in b_list:
    result = bin(b, a_list, 0, len(a_list)-1)
    print(result, end = ' ')

.

.

.

[풀이]

주어진 값이 리스트에 있는 값인지만 찾아주면 되는 간단한 문제라고 생각해서 처음에 틀렸다. 시간복잡도를 생각해야된다고 한다.

[정답1]처럼 list를 set로 변환시켜주기만 하면 시간초과가 해결된다. 엄청 간단하다.

근데 시간복잡도에 관한 이유는 아직 이해하지 못했다.

 

[정답2]는 binary search, 이분탐색을 이용한 코드다. while을 써도 되고 재귀로 해도 되는데 재귀로 연습해봤다.

 

p.s.

요즘 엄청 쉬운 문제를 헤매고 있다. 쉬운걸 쉽게 푸는게 좋긴 하겠지만 완벽히 이해하려다 보니 시간이 지체되나보다.

외우고 넘어가며 빠르게 많이 푸는 것이 좋은걸까

이해하며 꼼꼼히 천천히 풀어도 괜찮은걸까.