백준 1920번 : 수 찾기 (JAVA) 문제 풀이

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

1920번: 수 찾기

---

이제부터 열심히 알고리즘 문제를 풀어보아야겠다.. 하하

 

정말 간단한 문제인데, 시간 초과가 자꾸 떠가지고 삽질했다..

그냥 배열에 넣고 하나하나 비교했는데 -> 시간 초과

위 방법 + 배열 정렬 후 비교 -> 시간 초과

데이터들을 반으로 나눠서 비교하면 시간이 절반으로 줄을 것으로 예상!!

 

핵심 코드

for (int i = 0; i < M; i++) {
            int a = Integer.parseInt(st.nextToken());
            int mid = (arr.length / 2);     // 시간을 줄이기 위해서 범위를 반으로 나누기
            if (a >= arr[mid]) {            // 중간값과 비교하여 절반만 비교 수행
                for (int j = mid; j < arr.length; j++) {
                    if (arr[j] == a) {
                        result[i] = 1;      // 만약 값이 있다면? 결과배열에 1을 넣어주고 break!
                        break;
                    }
                }
            } else {
                for (int j = mid - 1; j >= 0; j--) {
                    if (arr[j] == a) {
                        result[i] = 1;
                        break;
                    }
                }
            }
}

 

절반으로 나눠서 비교해서 값이 있으면, result배열에 1을 넣어주도록 합니다.

끝~!!

 

전체 코드

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

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

        int N = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        int[] arr = new int[N];     // 입력 받은 값을 넣기 위해 배열 선언

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);           // 배열을 오름차순으로 정렬

        int M = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        int[] result = new int[M];
        for (int i = 0; i < M; i++) {
            int a = Integer.parseInt(st.nextToken());
            int mid = (arr.length / 2);     // 시간을 줄이기 위해서 범위를 반으로 나누기
            if (a >= arr[mid]) {            // 중간값과 비교하여 절반만 비교 수행
                for (int j = mid; j < arr.length; j++) {
                    if (arr[j] == a) {
                        result[i] = 1;      // 만약 값이 있다면? 결과배열에 1을 넣어주고 break!
                        break;
                    }
                }
            } else {
                for (int j = mid - 1; j >= 0; j--) {
                    if (arr[j] == a) {
                        result[i] = 1;
                        break;
                    }
                }
            }
        }

        for (int i : result) {
            System.out.println(i);
        }
    }
}