[백준] 1920번 수 찾기 (java)

<문제>

출처 : https://www.acmicpc.net/problem/1920

<나의 풀이>

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());
        int[] numbers = new int[N];    // 배열 만들어주기
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numbers);   // 정렬
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        int[] targets = new int[M];
        for (int i = 0; i < M; i++) {
            targets[i] = Integer.parseInt(st.nextToken());
        }   // M개의 수를 받아주는 배열 세팅.

        for (int i = 0; i < M; i++) {
            int min = 0;    // min 값의 인덱스
            int max = N - 1;    // max 값의 인덱스
            boolean hasNum = false;
            while (min <= max) {
                int mid = (min + max) / 2;
                // N의 값은 최대 100,000 이니까 합해봤자 200,000 아래임.
                // 그래서 mid 의 타입은 int 여도 됨.
                if (targets[i] == numbers[mid]) {
                    // targets[i] = 1; 여기서 타겟값이랑 넘버값이 같으면 값을 1로 바꿔줌.
                    hasNum = true;
                    break;
                } else if (targets[i] > numbers[mid]) {
                    min = mid + 1;
                } else {
                    max = mid - 1;
                }
            }
//            if (targets[i] != 1) {
//                // 여기서 실수인 것 같다. 타겟이 1이고 넘버에 1이 없을 때
//                // 그래도 타겟은 1일테니 0이 안들어가겠지.
//                targets[i] = 0;
//            }
            if (hasNum) targets[i] = 1;
            else targets[i] =0;
        }
        for (int i : targets) {
            System.out.println(i);
        }


    }
}

<다른 사람의 풀이>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
	public static int[] arr;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		// 배열은 반드시 정렬되어있어야한다.
		Arrays.sort(arr);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < M; i++) {
			
			// 찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력해야한다.
			if(binarySearch(Integer.parseInt(st.nextToken())) >= 0) {
				sb.append(1).append('\n');
			}
			else {
				sb.append(0).append('\n');
			}
		}
		System.out.println(sb);
	}
	
	
	/**
	 * @param key 찾으려는 값
	 * @return key와 일치하는 배열의 인덱스
	 */
	public static int binarySearch(int key) {
 
		int lo = 0;					// 탐색 범위의 왼쪽 끝 인덱스
		int hi = arr.length - 1;	// 탐색 범위의 오른쪽 끝 인덱스
 
		// lo가 hi보다 커지기 전까지 반복한다.
		while(lo <= hi) {
 
			int mid = (lo + hi) / 2;	// 중간위치를 구한다.
 
			// key값이 중간 위치의 값보다 작을 경우
			if(key < arr[mid]) {
				hi = mid - 1;
			}
			// key값이 중간 위치의 값보다 클 경우
			else if(key > arr[mid]) {
				lo = mid + 1;
			}
			// key값과 중간 위치의 값이 같을 경우
			else {
				return mid;
			}
		}
 
		// 찾고자 하는 값이 존재하지 않을 경우
		return -1;
 
	}
}

출처 : https://st-lab.tistory.com/261

<핵심 개념>

이진탐색에서 탐색 범위를 설정하기 위한 아이디어 떠올리기가 쉽지않았다.
문제 조건을 잘 봐야겠다. 그래야 삽질을 덜 할 것 같다.
n의 범위가 자연수였으면 int [] n = new int [n의범위+1] 로 풀 수 있을지도 모르겠다.

<피드백>

조건.. n의 조건을 제대로 생각하지 않아서 삽질을 좀 많이했다.
문제 조건은 언제나 중요하다. 주의하기.
그리고 Arrays.BinarySearch 메소드가 존재한다고 한다. (오오...)
그럼에도 직접 구현하는 연습을 게을리하지 않도록 하자.
Arrays.BinarySearch API 링크