person3113

늙어서 은퇴하기 전까진 계속 공부하자!!


난이도

  • 문제 접근하는 아이디어와 관점을 떠올리기 힘들었고, 책 설명을 봐도 이해하는 데 시간 걸렸다.
  • 교재 설명이 애매하고 구체적으로 설명하지 않아서, 다른 블로그 설명을 찾아봐서 참고했다.



문제

배열에서 k번째 수 찾기(Baekjoon: 1300번)

image



풀이

import java.util.Scanner;

public class test {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    long start = 1, end = K;
    long ans = 0;
    // 이분 탐색 수행
    while (start <= end) {
      long middle = (start + end) / 2;
      long cnt = 0;
      // 중간 값보다 작거나 같은 수는 몇 개인지 계산.
      for (int i = 1; i <= N; i++) {
        cnt += Math.min(middle / i, N);
      }
      if (cnt < K) {
        start = middle + 1;
      } else {
        ans = middle; // 현재 단계의 중간 값을 정답 변수에 저장
        end = middle - 1;
      }
    }
    System.out.println(ans);
  }
}



이해하기 어려웠던 부분

첫 번째

  • 시작 인덱스를 1로, 종료 인덱스를 k로 설정해서 오름차순으로 정렬한 B 배열을 탐색한 까닭은 교재에 매모했으니 참고

두 번째

if (cnt < K) {
  start = middle + 1;
} else {
  ans = middle; // 현재 단계의 중간 값을 정답 변수에 저장
  end = middle - 1;
}

image

  • if부분 이해(중간값보다 작거나 같은 수(cnt)가 K보다 작은 경우)
    • ex) k=7이라고 하자. 그리고 k번째 수(B[k])인지 테스트하고 싶은 수(middle)이 4라고 치자. 또 4보다 작거나 같은 것의 개수 cnt=6이라고 하자. 이 땐 1부터 4를 포함해서 4까지 카운트한 개수가 6개란 소리다. 즉 B배열에 인덱스 1~6까지 4보다 작거나 같은 수가 들어가 있고, 인덱스 7(찾고자 하는 k번째)에는 4보다 큰 다른 수가 들어있다고 해석 가능하다.
    • 따라서 우리가 찾고 싶은 k번째 수는 4보다 더 오른쪽에 있다는 소리니까 start값 늘려서, 다시 반복할 때 더 큰 middle값을 가지고 이게 k번째 수인지 확인할 수 있도록 한다.
  • else부분 이해(중간값보다 작거나 같은 수(cnt)가 K와 같거나 큰 경우)
    • ex) k=7이라고 하자. 그리고 k번째 수(B[k])인지 테스트하고 싶은 수(middle)이 6이라고 치자. 또 6보다 작거나 같은 것의 개수 cnt=8이라고 하자. 이 땐 B배열에 인덱스 1~8까지 6보다 작거나 같은 수가 들어가 있다. 하지만 cnt가 딱 k와 같지 않고 큰 경우, 인덱스 7(k번째)에는 5라는 수가 있고, 인덱스 8에 6인 경우와 같은 예외 상황이 생긴다.
    • 그럼 무턱대고 6을 7번째 수라고 결론지으면 안 된다. end를 줄여서 다음에 반복할 때 middle값을 더 낮춘다. 그리고 계속 탐색하면서 인덱스 7(k번째)에는 5라는 수가 있고, 인덱스 8에 6인 경우같은 상황이 있는지 파악한다. 끝까지 탐색할 때 동안(start<=end인 동안) 계속 cnt값이 k보다 작아서 계속 start 오른쪽으로 움직여서 계속 더 큰 middle값을 탐색해도 안된다. 이런 와중에 끝까지 탐색하면 다음과 같은 결론을 낼 수 있다.
    • 인덱스 7(k번째)에는 5라는 수가 있고, 인덱스 8에 6인 경우같은 상황이 있는지 전부 파악해보니 이런 경우는 없었다. 즉 위 그림처럼 인덱스 7과 8에 6이 들어있는 경우라고 결론지을 수 있다. 그럼 인덱스 7(k번째 수)는 6이라고 할 수 있다.

참고