[BOJ] 1920 수 찾기 - JAVA

1. 문제

1920번: 수 찾기

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

---

2. 풀이

• 배열을 정렬한다.(이분탐색에 필수)
• left = 0, right = N-1을 초기값을 주고 , left<=right일때 다음을 반복한다.
  • half에 (left+right)/2를, half로 찾아낸 배열 값을 halfVal에 저장한다.
  • 만약 숫자가 halfVal보다 크다면 오른쪽부분에 있다는 의미이므로 left를 half+1로 바꾼다.
  • 만약 숫자가 halfVal보다 작다면 왼쪽부분에 있다는 의미이므로 right를 half-1로 바꾼다.
  • 만약 숫자가 halfVal과 동일하면 반복을 끝낸다.
• 반복이 끝날때까지 값을 찾지 못했다면 그 배열에 해당 숫자가 없는 경우다.

import java.io.*;
import java.util.*;

public class BOJ_1920_수찾기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();

      int N = Integer.parseInt(in.readLine());
      int[] A = new int[N];

      StringTokenizer st = new StringTokenizer(in.readLine());
      for (int i = 0; i < N; i++) A[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(A);

      in.readLine();//M 필요없음
      st = new StringTokenizer(in.readLine());

      int num;
      while(st.hasMoreTokens()) {
         num = Integer.parseInt(st.nextToken());
         int left = 0, right = N - 1;
         boolean result = false;
         while (left <= right) {
            int half = (left+right)>>1;
            int halfVal = A[half]; 
            if (num > halfVal) left = half + 1;
            else if (num < halfVal) right = half - 1;
            else if (num == halfVal) {
               result = true;
               break;
            }
         }
         if(result) sb.append("1\n");
         else sb.append("0\n");
      }

      System.out.print(sb);
   }
}

---

3. 결과

되게 간단해보이는데 조건들이 한 끗 차이로 어긋나서 자꾸 틀렸다. left<right라고 했다든지.. 등등.

너무 궁금해서 Collections.binarySearch나 Arrays.binarySearch 함수를 보고 거기서 몇가지 참고해서 다시 제출했다.

 

1) A[half]로 매번 접근하지 않고 halfVal을 만들었다. 메모리는 조금 더 들었지만 시간이 줄었다.

2) half = (left+right)/2 하지 않고 half=(left+right)>>1로 바꿨다. 위의 함수에서는 >>>1이었는데 찾아보니 비슷한 용도고 나는 unsigned가 필요하지 않아서 >>만 했다. 이렇게 하니까 메모리가 아주,, 조금 줄었다.

3) 사실 캡쳐에는 없지만 몇 달 전에 맨 처음으로 푼 코드가 Arrays.binarySearch를 이용한 코드였다. 작동방식이 똑같은데도 왜 시간차이가 나나 궁금해서(그 코드는 520ms정도였다) 혹시나 하고 result부분을 수정했다. 

int result = 0; // 또는 1
sb.append(result).append("\n");

이 코드에서

boolean result = true;//또는 false

if(result) sb.append("1\n");
else sb.append("0\n");

이런 방식으로 바꿨더니 api 쓴 것 보다 시간이 더 줄어들었다. 아마 append도 줄이고, 같은 문자열을 여러번 사용해서 그랬을 거라고 추측된다.