[BOJ] 2776 암기왕 (Java)

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

 

앞선 문제에 이어 골라본 이분탐색 문제.

자신 있게 풀다가 잊고있던 StringBuilder의 위력을 다시금 일깨워주었다,,

 

package BOJ;

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

public class BOJ_2776 {

    static int T;
    static int n, m;
    static int[] arr;
    static StringBuilder sb;

    public static void binarySearch(int s, int e, int target){
        if(s > e) {
            sb.append("0");
            return;
        }
        int m = (s + e) / 2;
        if(arr[m] == target) {
            sb.append("1");
            return;
        }
        else if (arr[m] > target) {
            binarySearch(s, m-1, target);
        }else{
            binarySearch(m+1, e, target);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());

        while(T --> 0){
            sb = new StringBuilder();
            // 수첩 1
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);
            // 수첩 2
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<m; i++){
                int now = Integer.parseInt(st.nextToken());
                binarySearch(0, n-1, now);
                if(i != m-1) sb.append("\n");
            }
            System.out.println(sb.toString());
        }
    }
}

 

일단 이 코드의 절반은 입출력이다.ㅎ

선형탐색으로 하면 O(n*m) 이니 절대 안되고,

이분탐색을 재귀함수로 빼서 구현했는데 시간초과와 출력형식이잘못되었습니다를 무더기로 받았다.

 

무튼 코드 설명을 해보자면

1. 수첩1의 숫자를 배열로 받아 오름차순 정렬한다.

2. 수첩2의 숫자(target)를 하나씩 수첩1에서 찾아본다.

3. 이때, target이 mid(여기선 배열의 중간값이니 arr[m]) 값보다 작으면 e(end)를 m-1로 설정해서 재귀 호출한다.

4. target이 mid 값보다 크거나 같으면 s(start)를 m+1로 설정해서 재귀 호출한다.

5. s(start) 와 e(end) 범위가 교차하면 함수 종료.

 

이때!!

처음엔 0과 1을 System.out.println 을 사용해 바로 출력하였는데, 시간초과가 나서 StringBuilder로 변경하니 바로 해결

그리고 sb.append("0/n") 이런식으로 해주었더니 출력형식이잘못되었습니다가 떠서 다시 마지막값엔 개행을 제거하니 해결

 

무튼 결론은 StringBuilder를 애용하자!!!