알고리즘 챌린지 2일차

문제

문제: 백준알고리즘 1920번 수 찾기

풀이

• 먼저 N개의 숫자를 입력받아서 HashSet에 저장한다.
• HashSet은 중복을 허용하지 않으므로 중복은 걱정할 필요가 없다.
• M개의 숫자를 입력 받으면서 contains()를 이용해 입력받은 숫자가 HashSet안에 포함되어 있는지 확인한다.
• 포함되어 있을 경우 1, 아닐 경우 0을 출력한다.

Set을 이용한 코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> set = new HashSet<>();
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int temp = sc.nextInt();
            set.add(temp);
        }
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            int temp = sc.nextInt();
            if (set.contains(temp)) {
                System.out.println("1");
            } else {
                System.out.println("0");
            }
        }
    }
}

풀이

• 먼저 N개의 숫자를 입력받아서 A배열에 저장한다.
• A배열을 정렬한다.(자바의 기본정렬은 O(nlogn)의 시간 복잡도를 가지므로 정렬을 수행해도 시간초과가 일어나지 않는다.)
• M개의 숫자를 입력받으면서 각 명령을 실행한다.
  - 숫자를 찾았는지 판별해줄 find를 false로 정의한다.
  - 입력받은 타깃을 중간값과 비교한다.
  - 중간값이 타깃보다 크면 end 인덱스를 중간값-1로 대입한다.
  - 중간값이 타깃보다 작으면 start 인덱스를 중간값+1로 대입한다.
  - start가 end보다 크거나 같을 때까지 반복한다. 도중에 타깃과 같은 값을 찾으면 find를 true로 바꾼다.
  - 탐색이 끝난 후 find가 true면 1, false면 0으로 출력한다.

이진탐색을 이용한 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] A = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        Arrays.sort(A);

        int M = scan.nextInt();
        for (int i = 0; i < M; i++) {   //찾을 수의 개수 M 만큼 반복
            boolean find = false;
            int target = scan.nextInt();
            int start = 0;              // A배열 처음 인덱스
            int end = N - 1;            // A배열 마지막 인덱스
            while (start <= end) {      // 처음 인덱스가 마지막 인덱스와 같거나 작을때 반복
                int mid = (start + end) / 2;    // 중간값찾을 인덱스
                if (A[mid] > target) {          // 중간값이 타깃보다 크면
                    end = mid - 1;              // end 인덱스를 중간값 찾을 인덱스보다 하나 줄여 대입
                }else if (A[mid] < target) {    // 중간값이 타깃보타 작으면
                    start = mid + 1;            // start 인덱스를 중간값 찾을 인덱스보다 하나 늘려 대입
                }else {                         // 값을 찾았을때 반복문 종료
                    find = true;
                    break;
                }
            }
            if (find) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}

정리

처음에는 HashSet을 생각했다. 중복을 제거해주고 contains()메서드가 O(1)인 set이 적합할 것이라고 생각했다. 하지만 이 방법은 시간을 많이 잡아먹는다. 이진 탐색을 이용하여 푸는 것이 좀 더 효율적인 방법이다. 앞으로 데이터 탐색에는 시간복잡도가 logn인 이진탐색을 이용하자!