baekjoon(10815-숫자 카드)_python

1) 문제

 

2) 예시

3) 제출

<처음 낸 코드 - 시간 초과>

import sys
input = sys.stdin.readline

n = int(input())
nList = list(map(int, input().split()))
m = int(input())
mList = list(map(int, input().split()))

for i in range(0, len(mList)):
    if mList[i] in nList:
        mList[i] = 1
    else:
        mList[i] = 0

print(*mList)

<두 번째 낸 코드>

import sys
input = sys.stdin.readline

n = int(input())
nList = list(map(int, input().split()))
m = int(input())
mList = list(map(int, input().split()))

nList.sort()

def binary(target, data):
    start = 0
    end = len(data) - 1
    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            return True
        elif data[mid] < target:
            start = mid + 1
        else : end = mid -1
    return False

for i in range(0, len(mList)):
    if binary(mList[i], nList) == True:
        mList[i] = 1
    else:
        mList[i] = 0

print(*mList)

4) 메모리/시간/코드길이

5) PLUS

첫 번째 낸 코드에서 도저히 더 시간을 줄일 점을 찾지 못해서 알고리즘을 확인하니 이분 탐색이다.

그래서 이분 탐색 코드로 풀었는데 맞았다고 나왔고,

늘 그랬던 것처럼 맞은 다른 사람 코드를 확인했다.

그런데 내가 첫 번째 낸 거랑 비슷한 코드를 봤다,,

뭐가 그렇게 크게 다른지 몰라서 mList에 대입하는 방법 말고 문자열에 플러스하는 방법으로도 했는데 시간 초과 난다.

배열에 추가하는 방법X, 문자열에 늘려주기

시간 초과가 나는 이유를 리스트에 대입하는 방법에서 찾았다..

# 시간 초과가 나는 리스트 입력 방법
nList = list(map(int, input().split()))
mList = list(map(int, input().split()))

# 시간을 줄이는 리스트 입력 방법
nList = set(input().split())
mList = input().split()

map과 list 함수로 걸리는 시간이 꽤 된다.

map으로만 객체 생성하는 데에 시간이 꽤 걸린다.

https://m.blog.naver.com/happynut/222611329834

파이썬 - 리스트 생성 시 for, map, list의 시간 차이

이분 탐색으로 풀었지만 리스트 생성하는 함수에 관해 더 알게 되었다..

 

<이진 탐색 코드 설명>