[java] 문제 029 (백준 1920)

문제

수 찾기

 

교재 풀이

import java.util.Arrays;
import java.util.Scanner;
public class P1920_원하는정수찾기 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] 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++) {
      boolean find = false;
      int target = sc.nextInt();
      // 이진 탐색 시작
      int start = 0;
      int end = A.length - 1;
      while (start <= end) {
        int midi = (start + end) / 2;
        int midV = A[midi];
        if (midV > target) {
          end = midi - 1;
        } else if (midV < target) {
          start = midi + 1;
        } else {
          find = true;
          break;
        }
      }
      if (find) {
        System.out.println(1);
      } else {
        System.out.println(0);
      }
    }
  }
}

 

내 풀이) 24.6.14에 풀고 맞음

import java.util.*;
import java.io.*;

public class Main
{
    static int[] ns;
    static int[] ms;
	public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        
        ns=new int[n];
        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            ns[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(ns);
        
        int m=Integer.parseInt(br.readLine());
        ms=new int[m];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<m;i++){
            ms[i]=Integer.parseInt(st.nextToken());
        }
        
        for(int i=0;i<m;i++){
            System.out.println(bs(ms[i]));
        }
        
	}
	
	public static int bs(int target) {
	    int s=0;
	    int e=ns.length-1;
	    
	    while(s<=e){
	        int mid=(s+e)/2;
	        
	        if(target<ns[mid])
                e=mid-1;
            else if (target>ns[mid])
                s=mid+1;
            else 
                return 1;
	    }
	    
	    return 0;
	}

}


//	    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안에 존재하는지 알아내면 된다
//	    
//	    M개의 줄에 답을 출력
//	        존재하면 1을, 존재하지 않으면 0을 출력
//        
//        입력 
//            5
//            4 1 5 2 3
//            5
//            1 3 7 9 5
//        출력 
//            1
//            1
//            0
//            0
//            1
//        
//        접근법
//            n개의 수는 배열에 저장하고 : ns 
//            ns를 소트하고
//            
//            m개의 수도 배열에 저장한 후 : ms
//            
//            
//            for m번 반복하면서 
//                bs 메서드 사용
//            
//            bs 함수 구현 -> 1 혹은 0을 리턴함 / 인수는 s, e, target
//                s, e: 시작과 끝
//                mid = (s+e)/2 
//                target: ms[i]
//                
//                while s<=e 
//                    if(target<mid)
//                        e=mid-1 
//                    if else (target>mid)
//                        s=mid+1 
//                    else 같다면 
//                        1을 리턴 
//                0을 리턴

 

설명

1차 코드는 잘 안 되었다.

왜 그런지 챗 지피티에게 묻고 사소한 몇 가지를 고치고 맞았다 

int mid=(s+e)/2; => 이거를 while문 안에 넣어야 한다는 것 -> 처음엔 안에 안 넣었다 

target<ns[mid] => 처음엔 target < mid로 비교했다. mid는 인덱스지 값이 아닌데 말이다.

이런 점은 주의하자