[Java]자바 매개변수 탐색 - 배열에서 특정 수를 지우고 k번째 수를 찾는 방법

1. 문제

 

1부터 차례대로 숫자를 적는데, 3이나 5의 배수는 숫자 대신 "Moo"라고 적습니다. 예를 들어 1부터 16까지의 숫자를 적는다면 아래와 같습니다.

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

이 때, N번째로 적히는 숫자는 무엇인지 구하는 프로그램을 작성해보세요.

 

2. 풀이

 

이게 쉽나?? 되게 어려운데

 

이분탐색에 얽매이다보니 적절한 생각이 안드네

 

답을 보니까 약간 소름돋았다

 

배열에서 K번째 수를 어떻게 찾을 수 있을까?를 생각해본다면..

 

1부터 n까지 들어있는 배열 A에서, k번째 수를 나타내는 A[k]의 의미는?

 

k이하의 수가 k개라는 뜻이다.

 

배열에 빈 부분이 없으니까 이게 무슨소리야? 하겠지만..

 

그러면 이제 1부터 n에서 3의 배수, 5의 배수를 지우고 난다면...

 

1,2,4,7,8,11,13,14,16,.... 이렇게 나열이 될건데...

 

이러한 배열에서 3번째 수라는 뜻은?

 

A[3]은? A[3]이하는 총 3개있다는 뜻이다.

 

그러한 수는 위 배열에서 A[3] = 4이다.

 

4 이하로는 3개 있다는 뜻이 된다.

 

또 다른 예시로 7번째 수라는 뜻은?

 

A[7]은... A[7] 이하로 7개의 수가 있는 그러한 수로 A[7] = 13이다.

 

즉 13 이하로는 7개의 수가 있다는 뜻이다.

 

따라서, 3의 배수와 5의 배수가 지워진 배열에서 똑같이 적용해서, n번째 수를 찾고 싶다면,

 

k를 가정하고, k 이하의 서로다른 수의 개수가 n이 되는, k의 최솟값? 최댓값?

 

최솟값을 구하는게 적절할 것이다.

 

k이하의 서로다른 수의 개수가 n이라면, k는 n번째 수가 된다는 뜻이지

 

------------------------------------------------------------------------------------------------------------------------------------

 

k의 가능한 범위부터 생각해보면 1부터 넉넉하게 2n+1까지로 잡아주자

 

여기서 n이 10의 9승인데.. int의 범위가 2*10^9정도라서... int 넘어가지 않게 주의

 

import java.util.Scanner;

public class Main {

    public static int parametricSearch(int target, int start, int end){

        while(start < end){

            int mid = start + (end - start)/2;

            int param = mid - (mid/3 + mid/5 - mid/15);

            if(param >= target){
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        System.out.println(parametricSearch(n,1,2*n+1));

    }
}

 

 

1부터 mid 이하의 수 중에서 3의 배수나 5의 배수의 개수를 지우고 남은 수의 개수를 구해야할텐데,

 

어떻게 구할 수 있을까?

 

당장 mid이하에서 3의 배수의 개수는 어떻게 구할 수 있을까?

 

예를 들어 1부터 30까지 수 중에서 3의 배수의 개수는... 3,6,9,12,15,18,21,24,27,30으로 10개이다.

 

이는 30을 3으로 나눈 몫과 같다.

 

따라서 1부터 mid까지 3의 배수나 5의 배수를 지울려면, mid개에서 mid/3개와 mid/5개를 빼주고,

 

3의 배수와 5의 배수를 동시에 만족하는, 15의 배수의 개수를 더해줘야한다.

 

그렇게 구한 mid 이하의 수 중에서, 지워지지 않은 수의 개수가.. target = n 이상이라면..?

 

mid 이후로는 점점 target보다 커지니, mid 이전에 정답이 있을 가능성이 있어서 end = mid로 옮기고

 

target = n보다 작다면?? mid를 키워서, n에 맞춰나가야 하니 start = mid + 1로 옮겨야한다

 

param >= target이면, end = mid로 옮겼으니, 끝나고 end를 return해줘야겠지..?

 

 

 

핵심 아이디어는?

 

(정렬된) 수열에서 "k번째 수"가 a라는 것은? 

 

수열에서 a 이하의 개수가 k라는 뜻