숫자 카드

작성답안(오답)

package baekjoon;

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 nCount;
        int mCount;
        int[] answer;

        nCount = Integer.parseInt(br.readLine());
        int[] nArray = new int[nCount];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < nCount; i++) {
            if (st.hasMoreTokens()) {
                nArray[i] = Integer.parseInt(st.nextToken());
            }
        }

        mCount = Integer.parseInt(br.readLine());
        int[] mArray = new int[mCount];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < mCount; i++) {
            if (st2.hasMoreTokens()) {
                mArray[i] = Integer.parseInt(st2.nextToken());
            }
        }

        answer = calc(nArray, mArray);
        for (int i = 0; i < answer.length; i++) {
            System.out.println(answer[i] + " ");
        }
    }

    static int[] calc(int[] nArray, int[] mArray) {
        int lo;
        int hi;
        int mid;
        int target;
        int[] answer = new int[mArray.length];

        Arrays.sort(nArray);
        Arrays.sort(mArray);
        for (int i = 0; i < mArray.length; i++) {
            lo = 0;
            hi = nArray.length - 1;
            mid = (lo + hi) / 2;
            target = mArray[i];


            while (lo <= hi) {
                if (mid == target) {
                    answer[i] = 1;
                }
                if (mid < target) {
                    lo = mid + 1;
                }
                if (mid > target) {
                    hi = mid - 1;
                }
                answer[i] = 0;
            }
        }
        return answer;
    }
}

mArray의 원소가 nArray에도 있는지 검사하고, 있으면 1, 없으면 0을 반환하는 간단한 문제이다.
문제는 어려운게 없었으나 사소한 실수 2개로 인해 시간 안에 풀지 못했다.

• 실수 1) mArray[i]를 바탕으로 nArray에 동일한 원소가 있는지 파악을 하기 위해서는 mid가 첫번째 반복문이 아닌 두번째 반복문에서 업데이트 되어야 한다. 그런데 나는 첫번째 반복문에 선언하였으므로 계속해서 동일한 값을 할당하는 실수를 범했다.

• 실수 2) mid는 인덱스에 불과하다. 그런데 바보처럼 target과 비교할 때 array[mid]가 아닌 mid == target처럼 사용해버리는 실수를 했다.

• 실수 3) 이진탐색 대상의 배열에만 정렬을 해야하는데, 배열을 검사하는 배열(?)은 정렬하면 안된다!

정답

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 nCount;
        int mCount;
        int[] answer;

        nCount = Integer.parseInt(br.readLine());
        int[] nArray = new int[nCount];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < nCount; i++) {
            if (st.hasMoreTokens()) {
                nArray[i] = Integer.parseInt(st.nextToken());
            }
        }

        mCount = Integer.parseInt(br.readLine());
        int[] mArray = new int[mCount];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < mCount; i++) {
            if (st2.hasMoreTokens()) {
                mArray[i] = Integer.parseInt(st2.nextToken());
            }
        }

        answer = calc(nArray, mArray);
        for (int i = 0; i < answer.length; i++) {
            System.out.print(answer[i] + " ");
        }
    }

    static int[] calc(int[] nArray, int[] mArray) {
        int lo, hi, mid, target;
        int[] answer = new int[mArray.length];

        Arrays.sort(nArray);

        for (int i = 0; i < mArray.length; i++) {
            lo = 0;
            hi = nArray.length - 1;
            target = mArray[i];

            boolean found = false;
            while (lo <= hi) {
                mid = (lo + hi) / 2;
                if (nArray[mid] == target) {
                    answer[i] = 1;
                    found = true;
                    break;
                }
                if (nArray[mid] < target) {
                    lo = mid + 1;
                }
                if (nArray[mid] > target) {
                    hi = mid - 1;
                }
            }
            if (!found) {
                answer[i] = 0;
            }
        }
        return answer;
    }
}

배운점

1. 이진탐색을 할 때 mid는 인덱스 숫자에 불과하기 때문에 주의해야 함.
2. 이진탐색 중 mid는 항상 업데이트 되는 숫자이기 때문에 사용 위치를 주의해야함.
3. 자바에서 "2 3 4 5"와 같은 한 줄에 여러개의 숫자를 저장할 때 가장 효율적인 방법은 StringTokenizer와 while (st.hasMoreTokens())를 사용하는 것이다.

try {
            // 한 줄을 입력받음
            String line = br.readLine();
            
            // StringTokenizer를 사용하여 공백을 기준으로 숫자를 분리
            StringTokenizer st = new StringTokenizer(line);
            
            // 숫자들을 저장할 배열 또는 리스트 생성
            int[] numbers = new int[st.countTokens()];
            int index = 0;
            
            // 각 토큰을 숫자로 변환하여 배열에 저장
            while (st.hasMoreTokens()) {
                numbers[index++] = Integer.parseInt(st.nextToken());
            }
            
            // 배열 출력 (확인용)
            for (int number : numbers) {
                System.out.print(number + " ");
            }
            
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

4. 이진탐색 대상의 배열에만 정렬을 해야하는데, 이진탐색을 하는 배열은 정렬하면 안된다!