[BAEKJOON]1920 수 찾기

문제 요약

• 알고리즘 분류:  이분탐색, 해시
• 난이도: Silver4
• 문제내용:
  •  A 배열안에 존재 하는지 찾아라
• 사이트: https://www.acmicpc.net/problem/1920

1920번: 수 찾기

문제풀이

 이번 문제는 풀이 방법 두 가지를 설명 할것이다. 하나는 이분 탐색이고 다른 하나는 해시(key-value)로 풀것이다.

문제의 내용 보면 일반적으로 완전 탬색 할 경우에는 O(N^2)만큼 연산 해야 한다. N의 최대 개수가 10만  M의 최대 개수 10만에서 O(N^2)만큼 연산하면 시간 초과로 인하여 실패 한다. 그래서 이분 탐색이나 아니면 존재 하는지만 알면 되기 때문에 해시로 key-value로 저장해서 있으면 1 없으면 0으로 해야 한다. 정석으로는 이분 탐색으로 해야 하지만 존재 하는지만 알면 되기 때문에 해시로 간단하게 구현 할수 있다.

 일단 먼저 정석으로 이분탐색으로 하는 방법 부터 설명 하겠다. 이분 탐색 자세한 설명은 아래 글에 확인 해보면 된다.

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89  

이진 탐색 - 나무위키

  처음에는 찾는 수 존재 여부 관련 변수 하나 지정 하고 난 다음 이진 탐색을 진행 한다. 그리고  찾으면 존재 여부 관련 변수값을 1로 변경만 하면 끝이다. 아래 코드를 참고 하면 된다.

Python

# 시작점, 끝점, 배열안 존재 여부 초기화
start, end = 0, N - 1
isInNum = 0
# 이분 탐색
while start <= end:
    mid = (start + end) // 2 # 중간값 계산
    if A[mid] == num:
        isInNum = 1
        break
    elif A[mid] < num:
        start = mid + 1
    else:
        end = mid - 1

Java

int start, end, mid; // 시작점, 끝점, 중간점 변수
int isInNum; // A 배열안에 존재하는지 확인 하는 변수

for(int num : array) {
    // 이분탐색전 초기 설정
    start = 0;
    end = N - 1;
    isInNum = 0;

    // 이분 탐색
    while(start <= end) {
        mid = (start + end) / 2; // 중간값 계산

        // 찾을 경우 true로 변환하고 탐색 종
        if (A[mid] == num) {
            isInNum =  1;
            break;
        }else if(A[mid] < num) {
            start = mid + 1;
        }else {
            end = mid - 1;
        }
    }

 그 다음은 해시로 저장 하고 탐색 하는 방법인데 python에서는 dictionary라는 내장 자료 구조를 활용 하면 되고 java에서는 Map 자료 구조를 활용 하면 된다.

 python에서는 get(값, default value)로 처리 해서 아래 코드 처럼 있으면 1로 반환 하고 없으면 0으로 나오게 하면된다.

A.get(num, 0)

 Java에서는 getOrDefault(값, default value)로 처리 해서 아래 코드 처럼 있으면 1로 반환 하고 없으면 0으로 나오게 하면된다.

A.getOrDefault(num, 0)

Code

Python

이진 탐색

N = int(input())
A = list(map(int, input().split()))
A.sort() # 이분탐색을 위한 정렬
M = int(input())
array = list(map(int, input().split()))

for num in array:
    # 시작점, 끝점, 배열안 존재 여부 초기화
    start, end = 0, N - 1
    isInNum = 0
    # 이분 탐색
    while start <= end:
        mid = (start + end) // 2 # 중간값 계산
        if A[mid] == num:
            isInNum = 1
            break
        elif A[mid] < num:
            start = mid + 1
        else:
            end = mid - 1
    print(isInNum)

해시

N, A = int(input()), {i : 1 for i in map(int, input().split())}
M = input()

for num in list(map(int, input().split())):
    print(A.get(num, 0))

Java

이진 탐색

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		// A 배열 선언
		int[] A = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(A);

		// M개의 배열 선언
		int M = Integer.parseInt(br.readLine());
		int[] array = new int[M];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}

		int start, end, mid; // 시작점, 끝점, 중간점 변수
		int isInNum; // A 배열안에 존재하는지 확인 하는 변수

		for(int num : array) {
			// 이분탐색전 초기 설정
			start = 0;
			end = N - 1;
			isInNum = 0;

			// 이분 탐색
			while(start <= end) {
				mid = (start + end) / 2; // 중간값 계산

				// 찾을 경우 true로 변환하고 탐색 종
				if (A[mid] == num) {
					isInNum =  1;
					break;
				}else if(A[mid] < num) {
					start = mid + 1;
				}else {
					end = mid - 1;
				}
			}
			System.out.println(isInNum);
		}

	}

}

해시

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		Map<Integer, Integer> A = new HashMap<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			A.put(Integer.parseInt(st.nextToken()), 1);
		}

		// M개의 배열 선언
		int M = Integer.parseInt(br.readLine());
		int[] array = new int[M];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}

		for(int num : array){
			System.out.println(A.getOrDefault(num, 0));
		}

	}

}