[BaekJoon] 1920 수 찾기 JAVA

🔗 백준 1920 문제 https://www.acmicpc.net/problem/1920

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

---

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

풀이 1

문제를 봤을때 이해하는데에 시간이 걸렸지만 이해하고 나니 굉장히 쉽게 느껴졌다.

내가 이해한 문제는 이렇다.

1. N개의 정수 중 M개의 정수가 포함되는지 확인한다.

2. M개의 각 정수가 포함되면 1, 포함되지 않으면 0을 출력시킨다.

포함되는지 확인한다는 부분에서 contains() 를 활용하면 좋겠다고 떠올렸고 그를 토대로 코드 로직을 구현하였지만 시간초과가 발생했다.

문제를 상세히 보니 알고리즘 분류에 이진 탐색이 있는 것을 발견했다.

그리고 제한 시간이 1초인 것도 뒤늦게 발견했다..

시간 초과 코드

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

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());
        List<String> nList = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        while (n-- > 0) {
            nList.add(st.nextToken());
        }

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

        while (m-- > 0) {
            System.out.println(nList.contains(st.nextToken()) ? 1 : 0);
        }
    }
}

---

풀이 2

시간 제한과 이진 탐색을 확인하고 java.util.Collections 클래스에 Collections.binarySearch() 메서드가 있다는 것을 알게되었고 이를 활용하여 코드 로직을 구현하였다.

통과는 하였지만 시간이 너무 길게 나와 고민하다 보니 StringBuilder를 사용하여 각 결과를 문자열로 합쳐준 뒤에 출력을 시켜주니 1704ms → 776ms 로 확 줄었다.

그리고 Collections.binarySearch()메서드를 사용하는 것이 좋지 않다는 글을 본것같아 직접 이진탐색을 구현하여 로직도 구현해보았다.

ArrayList 1

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

// list + Collections.binarySearch
// 메모리 : 52960KB, 시간 : 1704ms

// list + Collections.binarySearch + StringBuilder
// 메모리 : 45168KB, 시간 : 776ms
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        List<String> nList = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while (n-- > 0) nList.add(st.nextToken());
        Collections.sort(nList);

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

        while (m-- > 0) {
            sb.append(Collections.binarySearch(nList, st.nextToken()) >= 0 ? 1 : 0).append("\n");
        }
        System.out.print(sb);
    }
}

ArrayList 2

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

// list + binarySearch
// 메모리 : 54424KB, 시간 : 1336ms

// list + binarySearch + StringBuilder
// 메모리 : 46912KB, 시간 : 760ms
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        List<Integer> nList = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while (n-- > 0) nList.add(Integer.parseInt(st.nextToken()));
        Collections.sort(nList);

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

        while (m-- > 0) {
            sb.append(binarySearch(nList, Integer.parseInt(st.nextToken())) >= 0 ? 1 : 0).append("\n");
        }
        System.out.print(sb);
    }

    private static int binarySearch(List<Integer> nList, int key) {
        int low = 0;
        int high = nList.size() - 1;

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

            if (key < nList.get(mid)) high = --mid;
            else if (key > nList.get(mid)) low = ++mid;
            else return mid;
        }
        return -1;
    }
}

---

풀이 3

시간을 더 줄여보고 싶은 마음과 Array와 List의 시간 차이를 비교해보고싶어졌고 Array를 활용하여 로직을 구현해보았다.

풀이 2 와 거의 비슷하다.

Array 1

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

// Array + Arrays.binarySearch
// 메모리 : 52652KB, 시간 : 1380ms

// Array + Arrays.binarySearch + StringBuilder
// 메모리 : 45660KB, 시간 : 604ms
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] nArr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) nArr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(nArr);

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

        while (m-- > 0) {
            sb.append(Arrays.binarySearch(nArr,Integer.parseInt(st.nextToken()))>=0?1:0).append("\n");
        }
        System.out.print(sb);
    }
}

Array 2

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

// Array + binarySearch
// 메모리 : 54776KB, 시간 : 1228ms

// Array + binarySearch + StringBuilder
// 메모리 : 44864KB, 시간 : 612ms
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] nArr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < n; i++) nArr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(nArr);

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

        while (m-- > 0) {
            sb.append(binarySearch(nArr, Integer.parseInt(st.nextToken())) >= 0 ? 1 : 0).append("\n");
        }
        System.out.print(sb);
    }

    private static int binarySearch(int[] nArr, int key) {
        int low = 0;
        int high = nArr.length - 1;

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

            if (key < nArr[mid]) high = --mid;
            else if (key > nArr[mid]) low = ++mid;
            else return mid;
        }
        return -1;
    }
}

---

풀이 3

알고리즘 분류 부분에 이진탐색 말고도 자료구조 가 적혀있었고 자료구조를 통해서도 시간제한 안에 구현이 가능한지 궁금해져 고민을 해 보니 HashSet을 활용하면 적합할거같다는 생각이 들었다.

HashSet은 중복을 제거함과 동시에 순서를 보장하지 않는다.

그리고 순서가 보장되지 않기 때문에 contains() 를 통해 값을 비교하게 되면 list, array보다 월등히 빠른 속도로 조회가 가능하다.

HashSet 1

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

// HashSet + StringBuilder
// 메모리 : 44952KB, 시간 : 564ms
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        HashSet<String> hashSet = new HashSet<>(); // 중복제거

        while (n-- > 0) hashSet.add(st.nextToken());

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

        while (m-- > 0) sb.append(hashSet.contains(st.nextToken()) ? "1\n" : "0\n");

        System.out.println(sb);
    }
}

HashSet 1.5

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

// HashSet + StringBuilder
// 메모리 : 44952KB, 시간 : 564ms
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        br.readLine();

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

        HashSet<String> hashSet = new HashSet<>(Arrays.asList(temp)); // 중복제거

        br.readLine();

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

        for (String s : temp) sb.append(hashSet.contains(s) ? "1\n" : "0\n");

        System.out.println(sb);
    }
}