백준 1920 - 수 찾기

문제링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

Note

이 문제는 N개의 정수 A[1], A[2], …, A[N] 중에서  입력된 정수가 있는지 없는지를 찾아야 하는 탐색(검색)문제이다.
사실 A[1], A[2], …, A[N] 중에서 특정 정수가 있는지 없는지 확인하기 위한 가장 간단한 방법은 선형(순차) 탐색(Linear Search) 알고리즘을 이용하여 처음부터 순차적으로 찾아보면 된다.

하지만 아래 코드는 시간초과가 발생한다. 즉 O(n) 인 선형탐색을 사용하지 말라는 뜻이다.

 
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
 
public class Main {
 
 
    public static void main(String[] args) throws IOException
    {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(bf.readLine());
 
        String []N = bf.readLine().split(" ");
        int m = Integer.parseInt(bf.readLine());
        String []M = bf.readLine().split(" ");
 
        List<Integer> list = Stream.of(N).map(c -> Integer.parseInt(c))
                .collect(Collectors.toList());
 
        Stream.of(M).map(c -> Integer.parseInt(c)).forEach(c -> {
            // 선형(순차)탐색으로 특정 숫자가 있는지 확인
            int result = 0;
            for(Integer integer : list) {
                if(c == integer) {
                    result = 1;
                    break;
                }
            }
            System.out.println(result);
        });
 
    }
 
}

사실 이 문제를  풀기위해서는 정렬(sort)와 이진탐색(Binary Search) 알고리즘을 알아야만 한다.
이진탐색은 자료가 많아도 평균적으로 O(log n)의 성능을 보여주기 때문에 시간초과를 피할 수 있다.
자바에서는 정렬과 이진탐색을 위한 코드를 직접 구현할 필요는 없고 Stream 의 sorted() 로 정렬을 하고 Collections.binarySearch() 를 사용해서 풀면 된다.
이제 시간 초과는 해결 되었다.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(bf.readLine());
        
        String []N = bf.readLine().split(" ");
        int m = Integer.parseInt(bf.readLine());
        String []M = bf.readLine().split(" ");
 
        List<Integer> list = Stream.of(N).map(c -> Integer.parseInt(c))
                .sorted().collect(Collectors.toList());
        Stream.of(M).map(c -> Integer.parseInt(c)).forEach(c -> {
            int i = Collections.binarySearch(list, c);
 
            System.out.println(i >= 0 ? 1 : 0);
        });
 
 
    }
 
}

이제 탐색이 O (c) 방법으로 풀어보자.
해당 정수가 있는지 없는지를 확인하기만 하면 되니 셋(Set) 자료구조를 이용하면 된다.
binarySearch() 를 사용했을때 보다 메모리는 조금 올라갔는데 시간은 조금 줄어든다.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
 
public class Main {
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(bf.readLine());
 
        String []N = bf.readLine().split(" ");
        int m = Integer.parseInt(bf.readLine());
        String []M = bf.readLine().split(" ");
 
        Set<Integer> set = Stream.of(N).map(c -> Integer.parseInt(c))
                .collect(Collectors.toSet());
        Stream.of(M).map(c -> Integer.parseInt(c)).forEach(c -> {
            System.out.println(set.contains(c) ? 1 : 0);
        });
 
 
    }
 
}

문제를 푸는 방법은 한 가지만 있는게 아니니 가장 최적의 해를 찾는 습관을 길들어야 한다.