[Java 자바] 백준 알고리즘 1920번 답 : 수 찾기

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

1920번: 수 찾기

 

 

이 문제 처음에 예제 입력만 보고 뭔소린지 이해가 안됐는데,, 맨 처음에 준 배열을 기준으로 두번째 배열의 값들이 존재하는지 1,0으로 구분하는 문제다. 

 

사실 이걸 과외학생이랑 파이썬으로 푼 적이 있어서 이진 탐색 문제인 것을 알고 있었다.

 

그래서 자바로 풀었는데,,ㅋㅋ 아니 자바에서 binarySearch 메소드 있는줄 모르고 처음에 그냥 짜서 품ㅋㅋ

아 참고로 이진탐색은 정렬된 배열에서 사용하는 겁니다...

순간 까먹고 함수 잘짰는데 왜 값이 이상하게 나오나하고,, 한참을 고민했읍니다,,,^^

 

[이진탐색 함수 직접 구현한 ver]

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

public class Main {
    public static int binary_search(int[] a, int target){
        int start = 0;
        int end = a.length-1;

        while(start <= end){
            int mid = (int)(start+end)/2;

            if(a[mid] == target)
                return 1;
            else if(a[mid] < target)
                start = mid+1;
            else
                end = mid-1;

        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int [] a = new int[N];

        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            a[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(a);

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

        for(int i=0;i<M;i++){
            sb.append(binary_search(a,Integer.parseInt(st.nextToken()))).append("\n");
        }
        System.out.println(sb);
    }
}

---

[Arrays.binarySearch 사용 ver]

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

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());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int [] a = new int[N];

        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            a[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(a);

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

        for(int i=0;i<M;i++){
            if(Arrays.binarySearch(a,Integer.parseInt(st.nextToken())) >= 0)
                sb.append(1).append("\n");
            else
                sb.append(0).append("\n");
        }
        System.out.println(sb);
    }
}

 

앗 참고로 Arrays.binarySearch(배열, 찾으려는 값) 이렇게 사용하면 되고, 찾으려는 값이 있으면 0 이상 값(찾은 인덱스)을 리턴해주고 없으면 0 미만의 값을 리턴해줍니당!

cf) 찾는 값이 없을 때는 배열의 정렬상태를 유지해줄 수 있는 인덱스 * (-1) -1 을 리턴해준다고 합니당~

 

---

[HashSet 사용 ver]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        HashSet<String> set = new HashSet<String>();
        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            set.add(st.nextToken());
        }

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

        for(int i=0;i<M;i++){
            String s = st.nextToken();
            if(set.contains(s))
                sb.append(1).append("\n");
            else
                sb.append(0).append("\n");

        }
        System.out.println(sb);
    }
}

 

다른 분들 풀이를 보니까 HashSet이나 HashMap을 사용하신 것도 많더라구요?! 

새롭게 배웁니당,, 

여기서 String 대신 Integer로 Set을 정의해도 되는데 String으로 했을 때 속도가 젤 빨랐어염!

 

Class2로 가면서 하루에 푸는 문제 수가 줄어들고 있네여ㅠㅡㅠ..

그래도 지식은 매일 늘어나는중!