[JAVA51] 1920. 수 찾기

1920. 수 찾기 (S4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	287633	91005	60108	30.364 %

문제

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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

출력

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

.

---

summary

수가 포함되어 있는지 확인

• 포함되면 1
• 포함되지 않으면 0 출력

 

strategy

자료구조(Set) 활용

• 10만을 이중 for 문 하면 시간초과 난다 (브루트 포스 X)
• HashSet 은 O(1) 로 찾을 수 있음
• 첫번째 배열은 Set 에 담음
• 두번째 배열값은 입력받을 때마다 Set 에서 찾기

 

note

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. 

import java.util.*;
import java.io.*;

public class Main {

    static int N, M;
    static Set<Integer> numbers = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());

        StringTokenizer input = new StringTokenizer(br.readLine());
        for(int n = 0; n < N; n++) {
            int num = Integer.parseInt(input.nextToken());
            numbers.add(num);
        }

        M = Integer.parseInt(br.readLine());
        input = new StringTokenizer(br.readLine());
        for(int m = 0; m < M; m++) {
            int num = Integer.parseInt(input.nextToken());
            if(numbers.contains(num)) answer.append(1);
            else answer.append(0);
            
            answer.append("\n");
        }

        System.out.println(answer);
        br.close();
    }
}

 

문제	결과	메모리	시간	언어코드	길이
1253	맞았습니다!!	50104 KB	580 ms	Java 11 / 수정	994 B

 

memo

• 투포인터도 생각했지만 두번째 배열은 정렬하면 안되서 탈락
• 이분탐색도 가능