[JAVA] 백준 이진탐색 - 실버모음(10815 숫자 카드, 10816 숫자 카드2, 1072 게임)

 

정렬관련 골드 문제를 풀다 이진탐색을 구현하는 연습이 부족하다는 걸 느꼈다. (start와 end 인덱스를 어디를 잡아야할 지 헷갈렸음)

그래서 이번 기회에 이진탐색 문제 몇 개를 풀어보려고 한다! 공부할 수록 공부해야할 게 늘어나는 것 같다 ㅎㅎ

 

 

 

 

이진탐색이란?

• 리스트를 두 부분으로 나눠 필요한 부분에서만 탐색하도록 제한하여 원소를 찾는 방법이다
• ex) [ 1 2 3 4 5 6 7 8 9 ] 와 같이 오름차순으로 정렬된 리스트가 있고 3을 찾아야한다
  • 일단 1~9번째 원소의 중간인 5를 본다
  • 5는 3보다 크니 탐색범위를 1~4로 줄인다
  • 1~4번째 원소의 중간인 2를 본다 
  • 2는 3보다 작으니 탐색범위를 3~4로 줄인다
  • .. 이 과정을 반복하여 3을 찾아냄
• 이진탐색을 위해서는 정렬이 필수적이며, 평균적으로 순차탐색보다 훨씬 빠르게 원하는 원소를 찾을 수 있다
• 관련 컬렉션: Arrays.binarySearch()

 

 

 

 

10815 숫자 카드 - 실버5

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

10815번: 숫자 카드

 

• 많은 숫자들 중 하나의 숫자가 존재하는 지 확인하는 문제이다
• 딱 봐도 이진탐색으로 풀지 않으면 시간초과가 날 것 같음

 

풀이법 생각

• 숫자 카드를 오름차순 정렬한다
• 찾아야하는 모든 숫자에 대해 이진탐색을 한 후 해당하는 값이 있으면 1, 없으면 0을 출력

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cardCnt = Integer.parseInt(br.readLine());

    int[] card = new int[cardCnt];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < cardCnt; i++)
      card[i] = Integer.parseInt(st.nextToken());

    int myCnt = Integer.parseInt(br.readLine());
    int[] my = new int[myCnt];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < myCnt; i++)
      my[i] = Integer.parseInt(st.nextToken());

    //오름차순 정렬
    Arrays.sort(card);

    StringBuffer sb = new StringBuffer();
    for (int num: my) {
      boolean isExist = isExists(num, card);

      sb.append(isExist?1:0); sb.append(" ");
    }

    System.out.println(sb);
  }

  private static boolean isExists(int num, int[] card) {
    int start = 0;
    int end = card.length;

    while (start < end) {
      int mid = (start + end)/2;

      if (card[mid] == num)
        return true;

      if (card[mid] > num)
        end = mid;
      else
        start = mid+1;
    }

    return false;
  }
}

• 정말 전형적인 이진탐색 문제인듯
• 활용은 전혀 없었따

 

 

 

10816 숫자 카드 2 - 실버4

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

10816번: 숫자 카드 2

 

• 이번엔 조금 활용버전이다
• 수가 적힌 숫자카드를 찾아내는 것 + 몇 장인지 구하는 것

 

첫 번째 생각한 풀이 - 이진탐색(시간초과)

• 일단 이진탐색으로 하나 찾아낸 후, 양쪽으로 가면서 같은 수가 몇 개 있는지 세면 될 것 같다
• 결말은 시간초과

 

두 번째 생각한 풀이 - 해시

• 해시를 사용해보려고 한다
• 숫자를 key값으로, 숫자의 빈도수를 value값으로 저장하여 빠르게 찾아볼 생각이다

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cardCnt = Integer.parseInt(br.readLine());

    Map<Integer, Integer> map = new HashMap<>();
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < cardCnt; i++) {
      int tmp = Integer.parseInt(st.nextToken());
      map.put(tmp, map.getOrDefault(tmp, 0) + 1);
    }

    int myCnt = Integer.parseInt(br.readLine());
    int[] my = new int[myCnt];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < myCnt; i++)
      my[i] = Integer.parseInt(st.nextToken());

    StringBuffer sb = new StringBuffer();
    for (int num: my) {
      int cntNum = 0;
      if (map.get(num) != null)
        cntNum = map.get(num);

      sb.append(cntNum); sb.append(" ");
    }

    System.out.println(sb);
  }
}

• 이진탐색으로 풀어야한다는 생각에 해시를 생각하지 못했다
• 10 10 10 10 10 10 10 10 ... 이런 경우 이진탐색이 그렇게 도움이 되지 않으므로, 그냥 해시를 쓰는 게 맞는 것 같음

 

+) 찾아본 다른 풀이

• 이진탐색으로 풀 수 있는 방법이다
• 다음 블로그를 참고하였다: https://st-lab.tistory.com/267
• 찾고자 하는 값의 가장 작은 인덱스를 찾는다 (lower_bound)
• 찾고자 하는 값의 가장 큰 인덱스를 찾는다 (upper_bound)
• 둘의 차이를 구하여 같은 수의 개수를 센다

 

 

 

 

1072 게임 - 실버3

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

1072번: 게임

 

 

풀이법 생각

• a는 추가로 이긴 횟수이다
• z에서 z+1로 될 때의 a의 값은 다음과 같은 식을 세워서 풀 수 있다

 

• z가 변하지 않는 경우는 다음과 같다. (z==100 || z==99)
  1. x와 y가 같다면 100에서 절대 변하지 않는다
  2. x와 y의 비율이 99라면 변하지 않는다. 99.xxx까진 갈 수 있어도 100으로는 절대 못간다
• z+1일 때의 a값은 소수점이 있을 확률이 높으니, Math.ceil을 사용하여 a의 최소 정수값을 구한다

 

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());

    long allCnt = Integer.parseInt(st.nextToken());
    long winCnt = Integer.parseInt(st.nextToken());
    long z = winCnt*100/allCnt;

    if (z == 100 || z == 99) {
      System.out.println(-1);
      return;
    }

    double tmp = (double)((z+1)*allCnt - 100*winCnt)/(99-z);
    int a = (int)Math.ceil(tmp);

    System.out.println(a);
  }
}