[코딩테스트]백준문제1920번 수 찾기

백준 문제

www.acmicpc.net/problem/1920

1920번: 수 찾기

문제 유형 : 해시, 배열, 구현

문제

N개의 정수 A[1], A[2], ..., A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], ..., A[N]이 주어진다. 다음 줄에는 M(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2³¹ 보다 크거나 같고 2³¹보다 작다.

출력

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

 

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

 

답안(PYTHON)

n = int(input())
A = set(map(int, input().split()))
m = int(input())
x = list(map(int, input().split()))

for i in x:
    if i not in A:
        print('0')
    else:
        print('1')

결과(PYTHON)

답안(PHP)

<?php
$n = readline();
$A = explode(" ", readline());
$m = readline();
$x =  explode(" ", readline());

foreach($x as $val) {
    if (in_array($val, $A) === FALSE) {
        echo '0' .PHP_EOL;
    } else {
        echo '1' .PHP_EOL;
    }
}

결과(PHP)

php는 제출 언어에 없다.

답안(Java)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private static int N;
	private static int[] A;
	public static void main(String[] args) {

		try (Scanner sc = new Scanner(System.in)) {
			N = sc.nextInt();
			A = new int[N];
			for (int i = 0; i < N; i++) {
				A[i] = sc.nextInt();
			}
			Arrays.sort(A);
			int m = sc.nextInt();
			for (int i = 0; i < m; i++) {
				int x = sc.nextInt();
				int left = 0;
				int right = A.length - 1;
				boolean flag = false;
				while (left <= right) {
					int midIdx = (left + right) / 2;
					int midVal = A[midIdx];
					if (midVal > x) {
						right = midIdx - 1;
					} else if (midVal < x) {
						left = midIdx + 1;
					} else {
						flag = true;
						System.out.println(1);
						break;
					}
				}
				
				if(!flag) {
					System.out.println(0);
				}
			}
			
			
		} catch(Exception ex) {
			
		}

				
	}
}

java는 다른 언어와 다르게 복잡함. list로 해서 작성하면 시간 초과가 나온다.

검색해보니 이분 탐색을 사용해야 한다고 나왔다.

현장에서 개발할 때는 그다지 시간이라던지 메모리에 대해 깊게 생각하지 않고 List는 빈번하게 사용했는데 이런 결과를 보니 그러한 행동들이 느리게 만드는 원인일지도 모르겠다.

그리고 한 가지 더 느낀 건 다른 언어보다 자바가 시간과 메모리를 엄청 잡아먹는다는 사실이다.

결과(Java)

참고사이트

www.acmicpc.net/problem/1920