백준 알고리즘 | 1920 : 수 찾기 (Python / 파이썬)

---

수 찾기 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	67437	20257	13238	29.782%

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

1920번: 수 찾기

---

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

​

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

​

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

알고리즘 분류

이분 탐색

---

 

백준 알고리즘 # 2579번 : 계단 오르기

출처:  https://wikidocs.net/1015

import sys

n = int(sys.stdin.readline())
N = set(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
M = list(map(int, sys.stdin.readline().split()))

for i in M:
    if i in N:
        print(1)
    else:
        print(0)

풀이

input()으로 입력을 받으니 계속해서 시간 초과가 나서

import sys를 한 뒤 sys.stdin.readline()을 사용해서 입력받았어요👏🏻

​

1. 먼저 정수의 개수인 n을 입력받은 뒤, N을 변수로 설정하여 A[1] ... A[N]처럼 리스트로 묶으면 되는데

여기서 리스트로 묶었을 때는 마지막 풀이에 계속해서 시간 초과가 나서

​

key point

구글링을 통해서 set을 이용해서 묶으면 된다는 것을 알고 { }으로 묶어줬어요.

[파이썬] 백준 1920번 - 왜 시간초과가 나는걸까? (feat. 자료구조 선택의 문제)

위 포스팅의 글을 보면 그 이유는 시간복잡도면에서 굉장히 간단합니다.

​

list의 search는 O(n), 직선적 시간으로 처음부터 원하는 값이 나올 때까지 if문을 돌릴 때 순차탐색을 하고

set의 search는 O(1), 상수 시간으로 알고리즘이 문제를 해결하는데 오직 한 단계만 거치게 되서

더 빠른 search가 이루어지고 시간초과가 안나는거죠!

 

(번역) 알고리즘 쉽게 이해하기 : 시간 복잡도와 Big-O 표기

아마도 set이 중복을 허용하지 않는 특징과 순서가 없다는 특징 때문에 그런 것 같네요!

​

2. 다음은 이제 간단하게 위에서 했던 방식과 동일하게 m을 변수로 설정하여 정수의 개수를 받고

M 변수로 list로 묶어주면서 입력받으면 준비 끝!

​

3. for문으로 M 리스트에 있는 숫자들을 차례대로 i 인자로 대입해주는데

여기서 if문을 사용해서 만약(if) i가 N에 있다면 그 즉시 1을 출력하고

아니라면(else) 0을 출력하면 문제 풀이 끄--읏👍🏻

​

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏🏻

wook2124/Algorithm-Test

최종 소스코드