[Python] 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을 출력한다.

---

풀이

1트

• 조건을 잘 보면 N도 100,000이고 M도 100,000이다.

  안보고 그냥 in조건으로 찾는 코드를 작성했더니 시간초과가 떴다ㅋㅋ

2트

• 내가 푼 방법은 A와 B를 정렬하여 앞에서부터 찾고 찾은 인덱스를 기억하여 다음에 찾을때 해당 인덱스부터 찾도록하는 방식이다.

  추가로 찾으려는 수 B가 A보다 커지면 찾기를 종료하고 마지막으로 비교한 인덱스를 반환한다.

  *B는 내가 정의한 문자이다. 문제에는 M개의 수를 받는다고 되어있다.

• 이 방식은 앞에 이미 한번 비교한 수들에 대해서는 다시 비교하지 않도록 만들기 때문에 효율적이다.

• 먼저 find_number함수에서 각 리스트를 정렬하고 B의 요소마다 find_in_a함수를 호출해 A안에 있는지 확인한다.

  B의 경우, 출력할때 순서대로 출력해야하므로 sorted를 사용했다.

• find_in_a에서는 인덱스를 기준으로 A가 B보다 더 커지지 않는 선에서 탐색해 결과와 인덱스를 반환한다.

• 결과를 순서에 상관없이 저장하기위해서 dict형식을 사용했다.

답

from sys import stdin

input = stdin.readline


def find_in_a(a, bn, idx):
    while idx < len(a) and a[idx] <= bn:
        if a[idx] == bn:
            return True, idx
        else:
            idx += 1
    return False, idx


def find_number(a, b):
    a.sort()
    idx = 0
    being = dict()
    for bn in sorted(b):
        flag, idx = find_in_a(a, bn, idx)
        if flag:
            being[bn] = 1
        else:
            being[bn] = 0
    return being


if __name__ == '__main__':
    N = int(input())
    A = input().split()
    M = int(input())
    B = input().split()
    res = find_number(A, B)
    for b in B:
        print(res[b])

---

다른 풀이

• 내가 처음에 풀었던 방식을 조금 바꿔서 list가 아닌 set에 수를 저장하고 찾는 식으로 구현하면 빠르게 찾을 수 있다고 한다.

• ⭐set은 iterable한 자료구조이지만 hash기반이기 때문에 검색이 훨씬 빠르다고 한다.

답

from sys import stdin
input = stdin.readline


if __name__ == '__main__':
    N = int(input())
    A = set(input().split())
    M = int(input())
    for num in input().split():
        if num in A:
            print(1)
        else:
	          print(0)

Uploaded by Notion2Tistory v1.1.0