[CodingTest] 1920 - 수 찾기

안녕하세요. 신뇽이 되고싶은 미뇽입니다!

오늘은 1920번 수 찾기를 풀어보겠습니다!

입력값

문제를 보고 생각한 해결 흐름

제한 시간이 1초이고 

 

중앙 피봇 퀵소트로 정렬 + 이분 탐색으로 값 존재 여부 찾기

 

구현

 

전역 변수

 

Main 함수

배열에 값을 모두 넣어줍니다.

 

그런다음 퀵소트 함수를 호출해줍니다.

 

퀵정렬 함수 

 

중앙값을 피봇으로 한 퀵정렬 코드입니다!

private static void quick_sort(int[] arr, int lo, int hi) {

    if (lo >= hi) {
        return;
    }

    int pivot = partition(arr, lo, hi);
    quick_sort(arr, lo, pivot);
    quick_sort(arr, pivot + 1, hi);

}

 

private static int partition(int[] arr, int left, int right) {

    int lo = left - 1;
    int hi = right + 1;
    int pivot = arr[(lo + hi) / 2];

    while (true) {
        do {
            lo++;
        } while (arr[lo] < pivot);

        do {
            hi--;
        } while (arr[hi] > pivot && lo <= hi);
        if (lo >= hi) {
            return hi;
        }
        swap(arr, lo, hi);
    }


}

 

 swap함수

 

서로 값을 바꿔주는 swap함수입니다.

private static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

 

메인함수에서 퀵정렬이 끝이 나면 이분탐색을 진행하고 결과를 StringBuilder에 append합니다.

 

이분탐색 코드

 

이분탐색 코드입니다.

private static int binarySearch(int key, int low, int high) {
//이분 탐색
     int mid;
     if (low <= high) {
         mid = (low + high) / 2;
         if (key == arr[mid]) {
             return 1;
         } else if (key < arr[mid]) {
             return binarySearch(key, 0, mid - 1);
         } else {
             return binarySearch(key, mid + 1, high);
         }
     }
     return 0;
 }

 

---

 

처음 시도 

60% 즈음에서 틀렸습니다가 나왔습니다.

반례가 너무 궁금하여 질물게시판에서 반례를 찾아왔습니다!

 

반례 입력값은 바로

5
1 2 3 4 5
1
3

위와 같은 입력이었는데요

 

에러 메세지가 index 1 out of bounds for length 1가 뜨면서 틀렸습니다가 떴던 것이었습니다.

오잉? 제가 StringTokenizer를 사용해서 

    st = new StringTokenizer(br.readLine(), " ");

이런식으로 코드를 짰는데

하나의 값이 들어오면 " "가 없어서 인식을 못하는 건가,,? 그럴리가 없는데...하면서 혼란이 왔습니다.

 

차근차근 코드를 다시 살펴보니 다른 곳에서 문제점을 발견했는데요!

 

바로 반복문에서 m까지만 돌려야하는 것을 n까지 돌려서 에러가 났던 것이었습니다! ㅎㅅㄹ,,

코드를 고친 후에 다시 돌려보니 해결 완료하였습니다!