[다른 방법으로 풀기] 2776. 암기왕

이전 풀이

https://aeongiii.tistory.com/87

이전에 HashSet를 사용해 풀이했는데 이번에는 다른 방법으로 풀어보려고 한다. 

결과부터 비교해보면 아래 표와 같다.

	기존 풀이 방식 (HashSet)	새로운 풀이 방식 (이분 탐색)
탐색 방식	HashSet.contains() 사용	Arrays.sort() 후 이분탐색
시간복잡도	O(N+M)	O(N log N + M log N)
메모리 사용	hashset에 저장, O(N)	배열에 저장하는 방식, O(N)
출력	BufferedWriter	StringBuilder -> System.out.println()
장점	탐색 속도 매우 빠름(O(1)) 정렬 필요 없음	메모리 적게 사용 정렬한 뒤에는 효율적
단점	HashSet의 O(N) 메모리 사용량 해시 충돌이 많아질경우 성능 저하	정렬하는 O(N log N) 시간 필요 이분탐색이 반복되므로 탐색 비용 증가

 

 

새로운 풀이

1. 문제 분석
    1) 각 테스트케이스에서 '수첩 2'에 적인 숫자 순서대로 '수첩1'에 적혀있으면 1을, 없으면 0을 출력한다.

2. 제약 조건
    1) 1 <= N <= 1,000,000
    2) 1 <= M <= 1,000,000
    3) 모든 정수의 범위는 int

3. 최초 의사결정
    1) 수첩 2에 적인 내용을 순서대로 출력하면서도 수첩1에 있는지 없는지를 다 확인해야 하므로, 정렬+이분탐색을 사용해 시간복잡도를 줄인다.
    2) T를 받고 각 T에 대해
    3) N을 받고 N배열에 저장, M을 받고 M배열에 저장한다.
    4) N배열을 sort한다.
    5) M을 하나씩 돌면서 이분탐색을 한다. (start, end, target)
        - half = end/2로 두고, target < half이면 0~half-1까지로 범위 변경한 뒤 다시 실행
        - half = End/2로 두고, target > half이면 half+1~0까지로 범위 변경한 뒤 다시 실행
        - half = M일 경우 끝


4. 문제풀면서 수정한 부분
    1) 재귀함수를 호출하기 전에 N <= half 여부를 검사하여 인덱스 초과 예외도 줄이고 0이 많이 붙는 오류도 수정했다.
    2) 메모리 초과 문제 : String[]을 int[]로 변경
    3) start = end가 될 경우 half도 계속 똑같아서 무한 루프에 빠질 수 있다. N <= half보다는 start>end가 더 적절하다.
    4) 메모리를 줄이기 위해 재귀가 아닌 while 반복문으로 범위를 줄여간다.
    5) 테스트케이스마다 sb 초기화

 

import java.io.*;

import java.util.*;

public class App {

    static StringBuilder sb = new StringBuilder();

    static int N;

    static int[] nArr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        while(T-- > 0) {

            // 테스트케이스마다 sb 초기화

            sb = new StringBuilder();

            N = Integer.parseInt(br.readLine());

            // nArr = br.readLine().split(" ");

            nArr = new int[N];

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

            for(int i = 0; i < N; i++) {

                nArr[i] = Integer.parseInt(st1.nextToken());

            }

            int M = Integer.parseInt(br.readLine());

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

            int[] mArr = new int[M];

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

            for(int i = 0; i < M; i++) {

                mArr[i] = Integer.parseInt(st2.nextToken());

            }

            // N배열 정렬

            Arrays.sort(nArr);

            for(int m : mArr) {

                search(m);

            }

            System.out.print(sb);

        }

    }

    private static void search(int target) {

        int start = 0, end = N - 1;

        while (start <= end) {

            int half = (start + end) / 2;

   

            if (nArr[half] == target) {

                sb.append(1).append("\n");

                return;

            } else if (target < nArr[half]) {

                end = half - 1;

            } else {

                start = half + 1;

            }

        }

   

        sb.append(0).append("\n");

    }

}

 

 

결론

N과 M의 크기가 크고 빠른 탐색이 필요한 문제이므로 HashSet이 더 유리할 것 같다.

만약 N배열이 이미 정렬된 상태로 주어지거나, 메모리가 제한적이라면 이분 탐색을 사용해야 할 것이다.