BOJ 1920 수 찾기

By kuper0201

Published in 알고리즘

2023-05-25

1 min read

문제

입력

풀이

문제

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

풀이

본 문제는 주어진 배열에서 특정 숫자가 존재하는지 확인하는 문제이다.

배열의 크기가 최대 100,000이기 때문에 $\mathcal{O}(N^{2})$ 의 시간 복잡도를 가지는 선형 탐색으로는 시간 초과가 발생한다.

Set을 이용하면 원소의 존재 여부를 $\mathcal{O}(1)$ 의 시간 복잡도 만으로 판별할 수 있다.

따라서 Set을 이용해 아래와 같은 로직을 구현하면 해당 문제를 풀어낼 수 있다.

원본 배열 입력 및 Set에 저장
탐색할 숫자 입력받고, 각 숫자가 Set에 존재하는지 확인
Set에 존재하면 1 출력, 그렇지 않으면 0을 출력

코드 보기(Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        HashSet<Integer> set = new HashSet<>();
        
        // 원본 배열 개수 입력
        int N = Integer.parseInt(br.readLine());
        
        // 원본 배열 입력 및 Set에 추가
        String[] s = br.readLine().split(" ");
        for(int i = 0; i < N; i++) set.add(Integer.parseInt(s[i]));

        // 탐색할 숫자 개수 입력
        int M = Integer.parseInt(br.readLine());
        
        // 탐색할 숫자 입력 및 Set에 존재하는지 판별
        s = br.readLine().split(" ");
        for(int i = 0; i < M; i++) {
            if(set.contains(Integer.parseInt(s[i]))) sb.append("1\n");
            else sb.append("0\n");
        }

        System.out.println(sb);
    }
}

코드 보기(C++)

#include <iostream>
#include <set>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    set<int> arr;
    
    // 원본 배열 개수 입력
    int N, M, T;
    cin >> N;
    
    // 원본 배열 입력 및 Set에 추가
    for(int i = 0; i < N; i++) {
        cin >> T;
        arr.insert(T);
    }
    
    // 탐색할 숫자 개수 입력
    cin >> M;
    
    // 탐색할 숫자 입력 및 Set에 존재하는지 판별
    for(int i = 0; i < M; i++) {
        cin >> T;
        if(arr.find(T) != arr.end()) cout << "1" << endl;
        else cout << "0" << endl;
    }
    
    return 0;
}

코드 보기(Kotlin)

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

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    var set: MutableSet<Int> = mutableSetOf<Int>()
    
    // 원본 배열 개수 입력
    var N = readLine().toInt()
    
    // 원본 배열 입력 및 Set에 추가
    var s = readLine().split(" ")
    for (i in 0 until N) {
        set.add(s[i].toInt())
    }
    
    // 탐색할 숫자 개수 입력
    var M = readLine().toInt()
    
    // 탐색할 숫자 입력 및 Set에 존재하는지 판별
    s = readLine().split(" ")
    for (i in 0 until M) {
        if(set.contains(s[i].toInt())) println("1")
        else println("0")
    }
}

코드 보기(Python)

from sys import stdin

def main():
    arr = set()

    # 원본 배열 개수 입력
    N = int(stdin.readline())

    # 원본 배열 입력 및 Set에 추가
    s = stdin.readline().split(' ')
    for i in range(N):
        arr.add(int(s[i]))

    # 탐색할 숫자 개수 입력
    M = int(stdin.readline())

    # 탐색할 숫자 입력 및 Set에 존재하는지 판별
    s = stdin.readline().split(' ')
    for i in range(M):
        if int(s[i]) in arr:
            print(1)
        else:
            print(0)

if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    var set = Set<Int>()
    
    // 원본 배열 개수 입력
    var N = Int(readLine()!)!
    
    // 원본 배열 입력 및 Set에 추가
    var s = readLine()!.split(separator: " ")
    for i in 0..<N {
        set.insert(Int(s[i])!)
    }
    
    // 탐색할 숫자 개수 입력
    var M = Int(readLine()!)!
    
    // 탐색할 숫자 입력 및 Set에 존재하는지 판별
    s = readLine()!.split(separator: " ")
    for i in 0..<M {
        if set.contains(Int(s[i])!) {
            print("1")
        } else {
            print("0")
        }
    }
}

main()