[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)1920번, 수 찾기

문제 링크

1920번: 수 찾기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이분 탐색이란 오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이분탐색에 자세한 내용은 링크를 남기겠습니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

예를들어(시작값 = 1, 최대값 = 9)

찾는 값 = 3, 중간값 = 5

1. 찾는 값이 중간 값보다 작으므로 최대값은 4가 된다.

1

2

3

4

5

6

7

8

9

시작값 = 1, 최대값 = 4 찾는값 = 3 중간값 = 2

2. 찾는 값이 중간 값보다 크므로 시작값은 = 3

1

2

3

4

5

6

7

8

9

시작값 = 3, 최대값 = 4 찾는값 = 3 중간값 = 33. 찾는 값과 중간값이 같으므로 3은 정렬된 숫자에 존재합니다.

1

2

3

4

5

6

7

8

9

이 문제에서는 이분 탐색을 사용하는 가장 기본적인 문제라고 할 수 있습니다.

입력값을 오름차순으로 정렬하여 이분 탐색을 통해 값이 존재하면 1 존재하지 않으면 0이 출력되게 하는 것입니다.

문제를 해결한 알고리즘의 과정입니다.

1. 입력값을 배열에 저장하여 오름차순으로 정렬하였습니다.

2. 범위(시작값 ~ 최대값)에서 중간값을 구합니다.

3. 중간값과 찾는 값을 비교하고 동일하면 1을 출력하고 크거나 작으면 시작값이나 최대값을 조정합니다.

4. 위 과정을 반복하여 배열에 동일한 수가 존재하지 않는다면 0을 출력합니다.

 

※중간값 구하는 공식 = (시작값 + 최대값) / 2

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 정수값 및 찾는 값을 나누었습니다.
• for문을 통해서 정수값에 대한 배열을 초기화하였습니다.
• 이분 탐색으로 찾는 값이 존재하는지 확인하는 find함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 찾는 값이 존재하는 여부를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• find함수에서 반복문을 통해 이분 탐색을 반복하는 과정을 하였습니다.
• 시작값과 최대값을 조정하면서 중간값을 이용하여 값이 존재하는지 확인하였습니다.
• 값이 존재하면 1을 반환 존재하지 않으면 0을 반환하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] arr;		//N개의 정수 저장 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        int size = Integer.parseInt(br.readLine());	//정수의 개수
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        arr = new int[size];	//배열 초기화
        for(int i=0;i<size;i++)
        	arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);		//배열 오름차순 정렬
        int M = Integer.parseInt(br.readLine());	//찾는 수 개수
        st = new StringTokenizer(br.readLine()," ");
        //-------함수 실행 및 BufferedWriter에 결과 저장--------
        for(int i = 0;i<M;i++) {
        	int num = Integer.parseInt(st.nextToken());
        	bw.write(find(num) + "\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //--------이분 탐색 함수----------
    public static int find(int n) {
    	int size = arr.length;
    	int start = 0;	//시작값
    	int end = arr.length-1;	//최대값
    	while(!(size==0)) {
    		int median = (start + end)/2;	//중간값
    		if(arr[median]==n) {	//찾는 값 동일한 경우
    			return 1;
    		}else if(arr[median]>n) {	//중간값이 찾는값보다 큰 경우
    			end = median-1;
    		}else {		//중간값이 찾는값보다 작은 경우
    			start = median + 1;
    		}
    		size /= 2;
    	}
       	return 0;		//배열에 찾는 값이 없을때 반환
    }
}