class2 - 1920번 수 찾기 (자바)

문제 : https://www.acmicpc.net/problem/1920

이 문제는 시간 제한이 1초로 굉장히 짧다.

그래서 이분탐색(이진탐색) 알고리즘을 사용해야 한다.

정말 놀라운 사실이.. 자바에는 이분탐색 함수가 이미 만들어져 있다!!!

그래서 손쉽게 풀 수 있었다.

 

문제에서 사용되는 개념

이분탐색(이진탐색)

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.

예시)

{1, 2, 3, 4, 5} 배열이 있고, 찾고자 하는 값은 2 이다.

가장 먼저 가운데 3을 찍어서 2가 3보다 큰지 작은지 같은지 비교하고, 3보다 작으면 왼쪽으로, 크면 오른쪽으로 가서 찾는다.

 

Arrays.binarySearch(arr, key) 

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html

배열에서 이분탐색을 하는 메소드.

오름차순된 배열 arr에서 key인 요소를 찾음.

검색 성공 시 : key와 일치하는 요소의 인덱스를 반환( 만약 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 반환 )

검색 실패 시 : 음수 반환

 

 

 

 

 

 

풀이

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

public class Main
{
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st;
            
            // 값 받음1
            int num1 = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] arr1 = new int[num1];
            for (int i = 0; i < num1; i++) {
                arr1[i] = Integer.parseInt(st.nextToken());
            }
            
            Arrays.sort(arr1); // 오름차순 정렬
            
            // 값 받음2
            int num2 = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] arr2 = new int[num2];
            int result;
            for (int i = 0; i < num2; i++) {
                arr2[i] = Integer.parseInt(st.nextToken());
                
                // 이분 탐색
                result = Arrays.binarySearch(arr1, arr2[i]);
                if (result < 0) bw.write("0\n");
                else bw.write("1\n");
            }
           
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}
		

	}
}

자바 Arrays 클래스의 Arrays.binarySearch(arr, key) 함수를 이용한 방법이다.

 

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

public class Main
{
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st;
            
            // 값 받음1
            int num1 = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] arr1 = new int[num1];
            for (int i = 0; i < num1; i++) {
                arr1[i] = Integer.parseInt(st.nextToken());
            }
            
            Arrays.sort(arr1); // 오름차순 정렬
            
            // 값 받음2
            int num2 = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] arr2 = new int[num1];
            for (int i = 0; i < num2; i++) {
                arr2[i] = Integer.parseInt(st.nextToken());
            }
            
            
            // 있는지 확인 - 이분 탐색
            for (int j = 0; j < num2; j++) {
                int result = 0; // 없음
                int end = arr1.length - 1; // 끝 인덱스
                int start = 0; // 시작 인덱스
                int middle = 0;
                while (true) {
                    middle = (end - start) / 2;
                    if (middle < 0 || end > arr1.length - 1) break;

                    if ( arr2[j] > arr1[middle]) {
                        start = middle + 1;
                    }
                    else if (arr2[j] < arr1[middle]) {
                        end = middle - 1;
                        // if (value == 0 && arr1[0] != arr2[j]) {
                        //     break;
                        // }
                    }
                    else if (arr1[middle] == arr2[j]) {
                        result = 1;
                        break;
                    }
                    
                }
                bw.write(String.valueOf(result) + "\n");
            }
           
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}
		

	}
}

이진 탐색을 수동으로 하는 코드이다.

 

 

문제 풀었던 과정

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

public class Main
{
	public static void main(String[] args) {
		try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st;
            
            int num1 = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] arr1 = new int[num1];
            for (int i = 0; i < num1; i++) {
                arr1[i] = Integer.parseInt(st.nextToken());
            }
            
            int num2 = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] arr2 = new int[num1];
            int result = 0;
            for (int i = 0; i < num2; i++) {
                arr2[i] = Integer.parseInt(st.nextToken());
                for (int j = 0; j < num1; j++) {
                    if (arr2[i] == arr1[j]) {
                        result = 1; // 존재함
                    }
                }
                
                bw.write(String.valueOf(result) + "\n");
                result = 0;
            }
        

           
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
          System.out.println("IOException 발생");
		}
	}
}

처음에 이런식으로 이분탐색을 사용하지 않고 풀었다가 시간초과가 났었다.

그래서 이분탐색 알고리즘을 사용하여 문제를 풀었다.