백준 1920번, 10815번-수 찾기, 숫자카드(JAVA)

1920번과 10815번 유형이 유사해서 같이 작성했습니다.

 

이진탐색(Binary Search) 알고리즘을 활용하는 문제입니다.

처음에 인텔리J상에서는 잘만 되는데 제출하니 자꾸 시간초과가 떠서

Scanner의 문제인가 하고 삽질을 했는데

알고보니 탐색법이 잘못되었더군요..(부족한 알고리즘 지식이 여기서-.-...)

 

저와 같은 분들을 위해 씁니다. 도움이 되셨으면 좋겠네요.

 

 

---

 

-1920번: 수 찾기

 

www.acmicpc.net/problem/1920

1920번: 수 찾기

N개 만큼의 수 배열과 M개 만큼의 수 배열이 각각 주어지고

M개 배열 중 N개 배열 안에 해당하는 수가 있다면 1, 없다면 0을 출력하는 문제입니다.

 

 

 

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //1920
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int[] arr1 = new int[N];
        int cnt=0;
        while(st.hasMoreTokens()){
            arr1[cnt++]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr1);

        int M= Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");

        int[] arr2 = new int[M];
        cnt=0;
        while(st.hasMoreTokens()){
            arr2[cnt++]=Integer.parseInt(st.nextToken());
        }

        int flag=0;

        int mid;

        for(int i=0;i<M;i++){
            flag=0;
            int low=0;
            int high=N-1;

            while(low<=high){
                mid=(low+high)/2;

                if(arr2[i]>arr1[mid]){
                    low=mid+1;
                }else if(arr2[i]<arr1[mid]){
                    high=mid-1;
                }else{
                   flag=1;
                   break;
                }
            }
            bw.write(flag+"\n");
        }

        bw.flush();

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

 

풀이과정

입력과 출력은 각각 BufferedReader와 StringWriter를 사용했습니다.

 

1. 개수 N을 받고, 입력받을 수는 StringTokenizer를 통해 받은 후 int배열 arr1에 옮겨줬습니다

 

2. 이진탐색을 위해선 비교대상이 정렬되어있어야 하므로 arr1을 Arrays.sort()로 오름차순 정렬해줍니다.

 

3. 1과 같은 방식으로 M만큼의 int배열 arr2에 입력받은 수를 옮겨줍니다.

 

4. 0과 1을 구분해두기 위한 flag를 선언해둡니다.

  

   이진탐색을 위해선 비교대상의(arr1) 최솟값, 중간값, 최댓값이 필요합니다. (인덱스)

   비교대상을 반으로 나눠서(arr1의 중간 인덱스 mid) 찾을값(인덱스 i순서로 찾을 arr2의 값)과 비교.

 

   

 

 

 

   case1) 찾을값이 비교대상의 mid 인덱스보다 클 경우, 최솟값인 low를 mid+1로 바꿔 범위를 좁힙니다.

 

     

   case2) 찾을값이 비교대상의 mid 인덱스보다 작을 경우, 최댓값인 high를 mid-1로 바꿔 범위를 좁힙니다.

 

   case3) 찾을값이 비교대상의 mid 인덱스와 일치할 경우엔 flag를 1로 바꾼 뒤 반복문을 빠져나옵니다.

 

 

   이런식으로 점점 비교 범위를 좁혀가다보면 일치하는 값이 생기거나(flag=1),

   while조건이 불일치하게 되어 flag는 여전히 0인 상태로 while문을 빠져나오게 됩니다.

 

   while문을 빠져나오면 flag의 값을 버퍼에 담습니다.

   arr2 인덱스 끝까지 훑으며 각각의 flag값이 write()메소드를 통해 버퍼에 담깁니다.

 

5. for문을 빠져나와 최종적으로 버퍼에 담긴 값을 flush()로 한번에 출력해줍니다.

 

   *flush()

    StringWriter의 메소드. 스트림을 비워줌과 동시에 담긴 값을 출력한다.

   

 

---

 

-10815번: 숫자 카드

 

www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

위와 비슷합니다. 다만 출력 방식이 다를 뿐..

 

N개 만큼의 수 배열과 M개 만큼의 수 배열이 각각 주어지고

M개 배열 중 N개 배열 안에 해당하는 수가 있다면 1, 없다면 0을 출력하는 문제입니다.

 

 

 

 

 

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

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

        //10815
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr1 = new int[N];

        String[] temp = (br.readLine()).split(" ");

        for(int i=0;i<N;i++){
            arr1[i]=Integer.parseInt(temp[i]);
        }
        Arrays.sort(arr1);

        int M= Integer.parseInt(br.readLine());
        int[] arr2 = new int[M];

        temp = (br.readLine()).split(" ");

        for(int i=0;i<M;i++){
            arr2[i]=Integer.parseInt(temp[i]);
        }


        int flag=0;

        for(int i=0;i<M;i++) {
            flag = 0;
            int low=0;
            int high=N-1;
            int mid;

            while (low <= high) {
                mid = (low + high) / 2;

                if (arr2[i] < arr1[mid]) {
                    high= mid-1;
                } else if (arr2[i] > arr1[mid]) {
                    low= mid+1;
                } else {
                    flag = 1;
                    break;
                }
            }
            bw.write(flag+" ");
        }

        bw.flush();

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

 

풀이과정은 위의 1920번과 같습니다.

다만 여기선 값을 입력받을 때 StringTokeneizer를 사용하지 않았고,

우선 String배열에 담은 후 int배열에 담아서 처리했습니다.