[소프티어] 자동차 테스트 자바 풀이 이진탐색 직접구현 함수사용 모두 해보기 (HSAT 7회 정기 코딩 인증평가 기출)

[소프티어] 자동차 테스트 자바 풀이 이진탐색 직접구현 함수사용 모두 해보기 (HSAT 7회 정기 코딩 인증평가 기출)

 

 

https://softeer.ai/practice/6247

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

 

 

 

핵심 설명

"중앙값이 나오는 서로 다른 경우의 수" 를 찾는 문제.

 

abcdef에서 c가 중앙값이라고 한다면 (정렬필수)

acd

ace

acf

bcd

bce

bcf

총 6가지다

 

그저 c의 인덱스를 찾고 이를 기준으로

왼쪽 길이 x 오른쪽 길이 하면 답 나온다.

2 x 3 처럼

(a,b) x (d,e,f) 처럼

 

 

 

 

 

풀어보니, 인덱스를 찾는 방법이 관건인 것 같다.

1. 첫 시도 실패 (순차탐색)

  // 제공함수 indexOf 사용
  public static int sol_fail(int find){
    return Arrays.asList(arr).indexOf(find);   // 시간초과 발생. 바이너리서치로 바꾸자
  }

테케는 풀리길래 제출해보니 20점..? 시간초과가 발생했다.

문제를 보면 * 1 ≤ 자동차의 연비 ≤ 1,000,000,000  이다.

10억개를 다 볼 순 없다

 

 

 

 

 

 

 

2. 두번째 시도 성공 (바이너리 서치 메서드 사용)

  // 제공함수 binarySearch 사용
  public static int sol_bi(int find){
    return Arrays.binarySearch(arr, find);   // 바이너리서치로 성공했는데 위에 직접 한번 짜보자.
  }

성공했다.

수행시간을 보니까 직접 구현하면 시간이 달라질까? 궁금하기도해서

이 김에 바이너리 서치 직접 구현해볼까? 싶었다.

 

 

 

 

 

 

3. 세번째 직접 구현

  // 직접구현
  public static int sol_handmade(int find){
    return my_binarySearch(0, n-1, find);
  }
  public static int my_binarySearch(int left, int right, int find){
      // System.out.println(left + " " + right + " " + find);
      if(left <= right){
          int mid = (left+right)/2;
          if(arr[mid] == find){
              return mid;
          }
          else if(arr[mid] < find){
              return my_binarySearch(mid+1, right, find);
          }
          else{
              return my_binarySearch(left, mid-1, find);
          }
      }
      return 0;
  }

역시나 성공했다.

수행시간은 더 빨라졌을까?

시간은 거기서 거기인거같다.

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#binarySearch-int:A-int-

Arrays (Java Platform SE 8 )

 

 

각설하고

 int mid = (left+right)/2; 로 중간값 확인해보고

find이면 리턴해주고

 

else if문과 else문에서는

소주병 뚜껑속 적힌 숫자로 술게임했었던

"업다운" 게임을 대입해보면 와닿을것이다.

 

그렇게 절반씩 탐색범위가 줄어드니

시간복잡도도 logN 으로 줄어든다.

 

일년에 술 몇번 먹는다고..

생각해보니 술 안먹은지도 오래됐는데

불타는 토요일 오늘 코테푸는 이 시간이 나에겐 더 재밌는 것 같다.

 

 

 

전체코드

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

public class Main {
    
  public static int dap = 0;
  public static int dx[] = {-1, 0, 1, 0};
  public static int dy[] = {0, 1, 0, -1};
  public static int n = 0;
  public static int q = 0;
  public static Integer arr[];
    
  public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    q = Integer.parseInt(st.nextToken());
    
    st = new StringTokenizer(br.readLine());
    arr = new Integer[n];
    for(int i=0; i<n; i++){
        arr[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(arr);
    
    for(int i=0; i<q; i++){
        int find = Integer.parseInt(br.readLine());
        
        // 위치 찾기
        // int findIndex = sol_fail(find);
        // int findIndex = sol_bi(find);
        int findIndex = sol_handmade(find);
        
        // 개수 세기
        if(findIndex+1>1 && findIndex+1<n){
            dap = (findIndex)*(n-findIndex-1);
        }
        else{
            dap = 0;    
        }
        
        bw.write(String.valueOf(  dap + "\n"  ));
    }
    bw.close();
  }
  
  // 직접구현
  public static int sol_handmade(int find){
    return my_binarySearch(0, n-1, find);
  }
  public static int my_binarySearch(int left, int right, int find){
      // System.out.println(left + " " + right + " " + find);
      if(left <= right){
          int mid = (left+right)/2;
          if(arr[mid] == find){
              return mid;
          }
          else if(arr[mid] < find){
              return my_binarySearch(mid+1, right, find);
          }
          else{
              return my_binarySearch(left, mid-1, find);
          }
      }
      return 0;
  }
  
  // 제공함수 binarySearch 사용
  public static int sol_bi(int find){
    return Arrays.binarySearch(arr, find);   // 바이너리서치로 성공했는데 위에 직접 한번 짜보자.
  }
  
  // 제공함수 indexOf 사용
  public static int sol_fail(int find){
    return Arrays.asList(arr).indexOf(find);   // 시간초과 발생. 바이너리서치로 바꾸자
  }
}

 

 

 

 

 

 

참고링크

https://adjh54.tistory.com/187

[Java/알고리즘] 이진 탐색(Binary Search) 이해하기

 

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

[알고리즘/Java] 이분 탐색 / 이진 탐색 (Binary Search)