BOJ_1920 수 찾기

• TOC {:toc}

이 글은 백준 온라인 저지의 1920번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.02 (Python)

import sys
input = sys.stdin.readline

LIMIT = 100000

A = [[] for _ in range(LIMIT)]
input()
for x in map(int, input().split()):
    A[x % LIMIT].append(x)
input()
for y in map(int, input().split()):
    print(1 if y in A[y % LIMIT] else 0)

디버그

• N과 M이 1과 100000 사이인 거지 입력받는 정수는 그것보다 더 많아서 x % 100000을 key로 잡으면 key가 중복될 수 있다.
  • key가 중복될 수 있는데 True, False로만 구분해서 틀렸다.
  • 각 key 별로 리스트를 만들어서 넣은 뒤 비교했다.

피드백

• 해시테이블을 써야 될 줄 알고 key를 겹치지 않게 만들 방법을 고민했었는데 그냥 x in A를 쓰면 됐었다.

참고 답안

import sys
input = sys.stdin.readline

# N과 M은 사용되지 않는다.
N, A, M = input(), set(input().split()), input()
print("\n".join((["1" if x in A else "0" for x in input().split()])))

2022.03.18

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

let [N, A, M, B] = input;

A = new Set(A.trim().split(" "));
B = B.trim()
    .split(" ")
    .map((b) => (A.has(b) ? 1 : 0));

console.log(B.join("\n"));

피드백

• 시간 초과를 피하려면
  • 매번 탐색하는 A를 Set 으로 만들어서 중복부터 없애 순회 시간을 줄이기
  • B의 각 원소마다 출력하지 말고 map을 이용해서 0과 1로 된 배열을 만들어 join으로 출력하기