백준 1920번 :: 수 찾기

한 달 만에 다시 풀게 된 문제, 눈물겨운 성장스토리 시작합니데이

 

한 달 전, 처음 풀 때는 이중for loop 돌도록해서 전체 탐색을 진행했었더랬지..

그때는 다른 방법을 쓸 수 없을 것 같았는데,

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        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[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] ans = new int[M];
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st2.nextToken());
            for (int num1 : nums) {
                if (num == num1) {
                    ans[i] = 1;
                    break;
                }
            }
        }

        for (int num : ans) {
            bw.write(num + " ");
        }

        bw.flush();
        bw.close();
    }
}

 

 

그리고 한 달이 지난 오늘, 이분탐색을 공부하고 다시 풀어보았다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);

        M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st2.nextToken());

            if (binarySearch(A, num)) sb.append("1").append("\n");
            else sb.append("0").append("\n");
        }

        System.out.println(sb);
    }

    private static boolean binarySearch(int[] arr, int num) {
        int leftIdx = 0;
        int rightIdx = N - 1;

        while (leftIdx <= rightIdx) {
            int midIdx = (leftIdx + rightIdx) / 2;
            int mid = arr[midIdx];

            if (num < mid) rightIdx = midIdx - 1;
            else if (num > mid) leftIdx = midIdx + 1;
            else return true;
        }
        return false;
    }
}

binarySearch라는 메서드를 구현, 로직은 정말 간단했다!

일단 중앙값으로 대소 비교를 해서 범위를 절반으로 좁혀가는 것임 그래서 비교해야할 배열은 무조건 정렬이 되어야 한다.

 

 

 

1. 처음에 풀었던 풀이의 시간/메모리

근데 왜 맞았습니다가 회색으로 바뀐거지..?

 

2. 오늘 새로 풀게된 풀이의 시간/메모리

 

메모리도, 시간도 다 절약이 된 걸 확인하였다.