지금 알고리즘 카테고리가 난장판이 됐는데... 그냥 싹 지우고 다시 만들어야 할 것 같다... ^^ 휴
그럼 오늘의 두 번째 리뷰 시작!

10815: 숫자 카드

1. 첫 번째 풀이: 실패

카드가 있느냐 없느냐를 판단하는 간단한 문젠데 시간 초과가 떠서 ㅋㅋ.. 굉장히 당황했다.

import sys

N = int(sys.stdin.readline().strip())
Nlist = list(map(int, sys.stdin.readline().strip().split()))

M = int(sys.stdin.readline().strip())
Mlist = list(map(int, sys.stdin.readline().strip().split()))

for j in Mlist:
    if j in Nlist:
        print(1, end=" ")
    else:
        print(0, end=" ")

Mlist에서 하나씩 받으면서 그 값이 Nlist에 있으면 1을, 없으면 0을 출력하는 로직이다. 이게 왜 시간 초과가 났을까 생각을 해보니까 굳이 Nlist들을 list로 받을 필요가 없다는 것을 깨달았다. 있냐 없냐만 판단하니까 중복이 없는 게 더 나을 것이다.

2. 두 번째 풀이: 성공

import sys

N = int(sys.stdin.readline().strip())
Nlist = set(map(int, sys.stdin.readline().strip().split()))

M = int(sys.stdin.readline().strip())
Mlist = list(map(int, sys.stdin.readline().strip().split()))

for j in Mlist:
    if j in Nlist:
        print(1, end=" ")
    else:
        print(0, end=" ")

이렇게 Nlist를 set으로 받으니까 시간 초과가 안나고 깔끔하게 되었다!

3. 다른 풀이

대부분의 분들은 이 문제를 이진 탐색으로 푸신 것 같다. 일단 나는 이진 탐색이 몬지 모른다 ^^... 숫자 카드 2에서 이진 탐색으로 풀어야 한다고 하는데, 그럼 그 때 해야지 ~~.. ㅎㅎ

오늘도 두 번째까지 끄읕!