[백준 1920] 파이썬 - 수 찾기

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

1920번: 수 찾기

 

# 조건

• 자연수 N이 주어진다.
• 다음 줄에는 N개의 정수 A[1] ---- A[N]이 주어지고
• 다음 줄에는 M
• 그 다음 줄에는 M개의 수들이 주어지는데, M개의 수들이 A안에 존재한다면 1, 아니면 0 출력
  
  

# 접근 방법

• 처음엔 리스트로 받아서 contain method in을 이용하여 제출
• 시간초과가 나서 이분탐색으로 접근하였다.
• 정렬을 해준 후, 가운데 인덱스부터 시작하여 작다면 왼쪽으로, 크다면 오른쪽으로 탐색 시작
• 시작점 (=start)과 탐색하게 될 인덱스(middle)이 같아진다면 수가 없으므로 0 출력

# 자연수 N이 주어진다.
# 다음 줄에는 N개의 정수 A[1] ---- A[N]이 주어지고
# 다음 줄에는 M
# 그 다음 줄에는 M개의 수들이 주어지는데, M개의 수들이 A안에 존재한다면 1, 아니면 0 출력

import sys
input = sys.stdin.readline

# A를 정렬 시킨 후 이분 탐색

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = int(input())
target = list(map(int, input().split()))


def search(num):
	# middle을 정해 줄 시작인덱스(0) , 마지막 인덱스(=N-1), 절반을 나눠줄 인덱스번호
    global start, end, middle
    while middle != start:
	    # A리스트의 시작인덱스, 마지막인덱스, middle인덱스와 찾는 수가 같다면 종료
        if num == A[start] or num == A[end] or num == A[middle]:
            return 1
        # middle인덱스의 수보다 작다면 end(현재 범위의 제일 큰수)를 middle로 변경후
        # middle 재계산
        elif num < A[middle]:
            end = middle
            middle = (start+end)//2
        # middle인덱스의 수보다 크다면 start(현재 범위 제일 작은수)를 middle로 변경 후
        # middle 재계산
        elif num > A[middle]:
            start = middle
            middle = (start + end) // 2

    return 0


for i in target:
    start = 0
    end = N - 1
    middle = (start + end) // 2
    print(search(i))

 

코드 제출 후 다른 사람의 코드를 보니 처음 내가 제출했던 in을 이용하여 푼 코드를 볼 수 있었다.

알고보니 

• list와 set 자료형의 차이에 있었다.
• set의 경우 list보다 in연산의 시간 복잡도가 1//N정도만큼 빠르다는 것을 알 수 있었다. remove 함수 또한 같은 차이가 난다!
• 이유는 파이썬의 set는 해시 테이블(hash table)로 구성되어 있어서 이다. 이에 대한 내용은 아래 게시글 참고

2022.09.09 - [CS/자료구조] - [자료구조] 해시(hash)

[자료구조] 해시(hash)

 

 

# N개의 정수가 주어져 있을 때 이, 안에 x라는 정수가 존재하는지 알아내라
# N개의 정수가 주어지고, X 정수 M개가 주어진다.

N = input()

target = set(map(int, input().split()))

M =input()

num = list(map(int, input().split()))
for i in num:
    if i in target:
        print(1)
    else:
        print(0)

위와 같이 단순히 set로 바꿔주니 시간 초과를 해결할 수 있었다.

 

자료 구조와 자료형에 대해 더 공부하는 것이 필요하다고 느끼는 오늘이였다!!