백준 1920 - 수 찾기 (자바 - 이분 탐색)

https://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 <= M <= 100,000) 이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A 안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31 보다 작다.

 

* 출력

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

 

* 예시

 

* 해결 과정

- 첫번째 해결 방법(TreeSet 사용)

TreeSet 은 Set 인터페이스를 구현한 클래스이기에 객체를 중복으로 저장할 수 없고 저장 순서가 유지되지 않는다는 Set 의 성질을 그대로 가지고 있다. 어차피 X 라는 숫자가 존재하는지 아닌지만 알아내면 되므로 중복되는 숫자가 입력으로 들어왔는지는 신경 쓸 필요 없다.

또한 TreeSet 은 이진 탐색트리의 구조로 이루어져 있음과 동시에, 그 중에서도 성능을 향상시킨 레드-블랙트리로 구현되어 있다.

* 레드-블랙트리 : 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우져지지 않도록 균형을 맞추어준다.

이와 같은 형태로 데이터가 저장되기 때문에 기본적으로 오름차순 정렬이 지원된다.

그러므로 주어진 숫자들 중 특정 숫자 X 가 존재하는지 알아낼 때 자료구조 내부에서 데이터를 탐색하는데 있어 자연스레 이분탐색 방식이 적용되어 특정 숫자 X 를 찾게된다.

 

이와 같이 TreeSet 클래스를 활용해서 문제를 해결한다면 아래와 같은 로직을 설계할 수 있다.

1. TreeSet 자료구조에 입력받은 숫자들을 저장한다.

2. 찾고자 하는 숫자들을 하나하나 TreeSet 에서 찾아가며 TreeSet 에 찾고자 하는 숫자가 존재하는 경우 1, 존재하지 않는 경우 0 을 출력한다.

* TreeSet 에서 데이터를 탐색할 때 root node 는 레드-블랙트리의 데이터 저장 원리에 의해 오름차순 정렬된 데이터들 중에서 중간값에 가장 가까운 값에 해당된다. 그러므로 root node 에서 부터 데이터를 찾기 시작하는데 왼쪽 자식 노드는 부모 노드보다 작은값, 오른쪽 자식 노드는 부모 노드보다 큰 값이 저장되는 원리에 따라 특정 숫자 X 를 찾을 때 자동으로 이분탐색 원리로 데이터를 찾게 된다.

 

* 코드 1

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		TreeSet<Integer> numberList = new TreeSet<Integer>();
		int count = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < count; i++) {
			
			numberList.add(Integer.parseInt(st.nextToken()));
		}
		
		int testCount = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < testCount; i++) {
			if(numberList.contains(Integer.parseInt(st.nextToken()))) {
				bw.write(1 + "\n");
			}
			else {
				bw.write(0 + "\n");
			}
		}
		bw.flush();
		bw.close();
	}
}

 

- 두번째 해결 방법 (이분탐색 직접 사용)

TreeSet 클래스를 활용하는 방법은 자바에서 직접 구현된 클래스를 이용해서 너무 쉽게 넘어간듯 해 이분탐색 알고리즘을 직접 구현하는 방식으로도 풀어보았다.

1. 입력받은 숫자들을 배열에 저장한 후 오름차순 정렬

2. 찾아야 할 숫자들을 순서대로 이분탐색을 통해 배열에서 찾는다.

- start = 0, end = 배열 길이 - 1 로 초기화 한다.

- start <= end 조건을 만족하는 동안 반복문을 진행하며 mid 변수에 (start + end) / 2 값을 저장한 다음, mid 값을 인덱스로 하여 배열을 탐색할 때 해당 인덱스의 값과 찾고자 하는 변수가 일치하면 반복문을 즉시 종료하고 1을 출력해준다.

- mid 값을 인덱스로 하여 배열을 탐색할 때 해당 인덱스의 값이 찾고자 하는 변수보다 크다면 end 를 mid - 1 값으로 초기화 해주고 다음 반복으로 넘어간다.

- mid 값을 인덱스로 하여 배열을 탐색할 때 해당 인덱스의 값이 찾고자 하는 변수보다 작거나 같다면 start 를 mid + 1 값으로 초기화 해주고 다음 반복으로 넘어간다.

- 반복문 중간에 배열에 mid 인덱스에 해당하는 숫자가 찾고자 하는 변수와 같은 경우를 찾지 못한 경우 0을 출력한다.

 

* 코드 2

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().solution();
	}

	private void solution() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int size = Integer.parseInt(br.readLine());
		int[] numberArray = new int[size];
		String[] input = br.readLine().split(" ");
		for (int i = 0; i < input.length; i++) {
			numberArray[i] = Integer.parseInt(input[i]);
		}

		Arrays.sort(numberArray);

		size = Integer.parseInt(br.readLine());
		input = br.readLine().split(" ");
		for (int i = 0; i < size; i++) {
			int numberX = Integer.parseInt(input[i]);

			int start = 0;
			int end = numberArray.length - 1;
			boolean find = false;
			while (start <= end) {
				int mid = (start + end) / 2;

				if (numberArray[mid] == numberX) {
					find = true;
					break;
				} else if (numberArray[mid] > numberX) {
					end = mid - 1;
				} else {
					start = mid + 1;
				}
			}

			if (find) {
				bw.write(1 + "\n");
			} else {
				bw.write(0 + "\n");
			}
		}

		bw.flush();
		bw.close();
		br.close();
	}
}

 

입력받은 데이터들을 배열에 저장하고 오름차순 정렬해주고 난 뒤, 해당 숫자를 특정 조건에 따라 범위를 좁혀가며 찾았으므로 이분탐색 문제에 해당된다.