10815

 

 

파이썬 내장 정렬 함수와 리스트를 사용해서 풀이한 뒤 순서만 다르게 나와서 진짜 약올랐는데 바보는 나였다.

정렬해버리니까 당연히 안나옴;

 

작년에 스터디할 때 디폴트딕셔너리 같은게 있었던 것 같아서 그걸 이용해서 풀어야겠다고 생각했다.

from collections import defaultdict

N = input()
n = map(int,input().split())

M = input()
m = list(map(int,input().split()))

result = []

#defaultdict 생성
ndict = defaultdict(int)
for i in n:
    ndict[i] = 1

for i in m:
    result.append(ndict[i])
print(result)

근데 틀림.. 왜 테케는 잘 돌아갔는데 왜 틀린건지 생각해보면 정수 범위를 신경안쓴게 걸린다. long 타입으로 바꾸려고 하는데...

무슨 일인지 패키지를 설치하고 임포트해도 해결되지 않는다 찾아본 바로는 long과 int가 합쳐졌다는 것 같은데 그럼 어떻게 해야하는거죠?

 

일단 해결을 못해서 문제에서 원하는 대로 이진탐색으로 풀어보려고 한다....

 

import sys
input = sys.stdin.readline

N = int(input())
n = list(map(int, input().split()))

M = int(input())
m = list(map(int, input().split()))

result = [0]*M

n.sort()
# 이진탐색
for i in range(M):
    l = 0
    r = len(n) - 1

    while(l<r):
        idx = int((l + r) / 2)
        if m[i] == n[idx]:
            result[i] = 1
            break
        elif m[i] > n[idx]:
            l = idx
        else:
            r = idx

print(result)

이진탐색 구현했는데 계속 시간 초과가 뜸

 

import sys
input = sys.stdin.readline

N = int(input())
n = list(map(int, input().split()))

M = int(input())
m = list(map(int, input().split()))

result = [0]*M

n.sort()
# 이진탐색
for i in range(M):
    l = 0
    r = N - 1

    while(l<=r):
        idx = int((l + r) / 2)
        if m[i] == n[idx]:
            result[i] = 1
            break
        elif m[i] > n[idx]:
            l = idx+1
        else:
            r = idx-1

print(*result)

통과된 최종 코드

print(*list) 형식 알아두기

 

인덱스 딕셔너리에 저장하는 numInfo = {v: i for i, v in enumerate(chkLst)}

알아두기

 

#이진탐색