[백준] 수 찾기(1920) (JAVA)

안녕하세요 코밑이에염!

모두 오랜만이에요!

요즘 현생이 바빠서 블로그에 소홀해진 거 같아요 ㅠ

다시 한번 달려볼게요!!!

 

오늘의 포스팅은 백준 수 찾기에요!

자신이 입력한 숫자만큼 배열에 숫자를 입력하고

또 자신이 입력한 숫자만큼 숫자를 입력해요

 

먼저 입력한 숫자들은 비교할 대상이 되고

나중에 입력한 숫자들과 비교하게 되요

같은 숫자가 있다면 1

없다면 0이 출력되게 됩니다!

 

바로 요렇게요!!!

 

이해가 되셨을까요???

그럼 코드 설명하겠습니다!!!

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

public class BinarySearchTree {
	int BinarySearch(int A[], int val, int low, int high) {
		if (high < low) // 배열의 길이가 0일 때
			return 0;

		int mid = (low + high) / 2; // 중간 인덱스, 중앙값은 2

		if (A[mid] > val) // 만약 중앙인덱스가 비교값보다 크면
			return BinarySearch(A, val, low, mid - 1); // high 1칸 하강

		else if (A[mid] < val) // 만약 중앙인덱스가 비교값보다 작으면
			return BinarySearch(A, val, mid + 1, high); // low 1칸 상승

		else if (A[mid] == val) // 같아지면
			return 1; // 1 반환

		else // 안 같으면
			return 0; // 0 반환
	}

	public void input() {
		Scanner sc = new Scanner(System.in);
		int A[];

		int n = sc.nextInt();
		A = new int[n];

		for (int i = 0; i < n; i++) {
			A[i] = sc.nextInt(); // 트리 입력값
		}

		Arrays.sort(A); // 서순 정렬 한번 1 2 3 4 5

		for (int i = 0; i < n; i++) { // 출력
			System.out.printf(A[i] + " ");
		}

		int m = sc.nextInt();

		for (int i = 0; i < m; i++) {
			int B = sc.nextInt(); // 비교값
			// 입력받은 배열, 비교 값, 최소값,
			System.out.println(BinarySearch(A, B, 0, A.length - 1));
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BinarySearchTree bst = new BinarySearchTree();
		bst.input();
	}
}

이진 탐색 트리를 이용해 보았어요!

 

이진탐색트리는 이진 트리의 일종으로 각 노드는 값을 포함하고 있어요!

빠른 검색, 삽입, 삭제를 지원하는 자료 구조로 널리 사용됩니당!

 

 

1. 노드의 왼쪽 서브트리에 있는 모든 노드들은 해당 노드의 값보다 작다

2. 노드의 오른쪽 서브트리에 있는 모든 노드들은 해당 노드의 값보다 크다

3. 양 쪽 모두 이진 탐색 트리여야 한다

 

이런 특징을 가지고 있답니다~

 

이런 모습이에요!

이러한 자료구조 형태를 사용한다면 쉽게 해결할 수 있겠죠!?

 

 

그럼 다음에 다시 올게용!