[java 백준] 실버 4/10815번 숫자카드

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

10815번: 숫자 카드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static int m;
    public static long[] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n = Integer.parseInt(br.readLine());
        arr = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        m = Integer.parseInt(br.readLine());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
 
            int startIdx = 1;
            int endIdx = n;
 
            while (startIdx <= endIdx) {// 등호 --> 찾고자하는 값이 -10일때 문제 생김
 
                int midIdx = (startIdx + endIdx) / 2; // 얘가 while문 안에 있어야
                if (target >= arr[midIdx]) {
                    startIdx = midIdx + 1;
                } else {
                    endIdx = midIdx - 1;
                }
            }
 
            if (arr[endIdx] == target) { // startIdx값은 변질이 생겨도 endIdx 값은 변질이 생기지 않음
                System.out.print(1 + " ");
 
            } else {
                System.out.print(0 + " ");
 
            }
 
        }
 
    }
 
}
 

문제 풀면서 염두해 두어야 할 것 

 

 

1) int midIdx = (startIdx + endIdx) / 2; <-- 이게 반드시 while문 안에 있어야한다.

너무 당연하다 느껴지겠지만 난 자꾸 mid값을 while문 밖에다 써줘서 골치아팠다. 생각해보면 startIdx와 endIdx값이 바뀔때마다 중간값을 새롭게 바꿔줘야하니 while문 안에 쓰는건 당연하다. 잊지 말자. 

 

2)while (startIdx <= endIdx) <-- 여기에 등호가 필요하다.

예를 들어 내가 찾고하는 값이 -10이라 해보자.

그리고 숫자카드는

6 3 2 10 -10

이 있다.

얘네를 오름차순 정렬하면

 

-10 2 3 6 10이 될거다.

 

이제 이진탐색을 해보면 startIdx=1 endIdx=5 midIdx=3이 된다.

arr[3]=3이기 때문에 (arr의 인덱스가 1부터 시작합니다)

-10<3이다. 그렇기에 endIdx=midIdx-1을 해주면 startIdx=1 endIdx=2 midIdx=1이 된다.

midIdx[1]=-10이니까 우선 얘를 keep해두고 이진탐색 끝까지 가보자. 그러면

startIdx=2 endIdx=2 midIdx=2가 된다. 이럴때 만약 while(startIdx<endIdx)였다면 while문을 빠져나와서

endIdx=2가 될거고

arr[endIdx]==target이라는 조건문을 만났을때 0을 출력할거다.

 

그런데 -10은 이 숫자카드 안에 있기에 1을 출력해야한다.

 

그렇기에 while(startIdx<=endIdx)로 등호를 붙이면

startIdx=2 endIdx=2 midIdx=2일때 arr[2]>-10이 되기에 endIdx=1로 변하면서 

startIdx>=endIdx가 되기에 while문을 빠져나간다. 그러면 이때 arr[endIdx]=-10 target=-10이 면서 숫자카드에 찾고자하는 값이 있다는 1을 출력할 수 있다. 

 

 

3) 문제를 풀면서 만났던 에러들 

 

- ArrayIndexOutOfBounds 에러

0부터 시작하면 헷갈려서 arr배열도 1부터 n까지 startIndex와 endIndex도 1부터 n까지 설정해주니 에러가 해결되었다. 

 

- 시간초과 에러

Scanner 말고 BufferedReader,StringTokenizer로 바꿔주니 해결되었다.