[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)1300번, K번째 수

문제 링크

1300번: K번째 수

 

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이분 탐색이란 오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이분탐색에 자세한 내용은 링크를 남기겠습니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

예를들어(시작값 = 1, 최대값 = 9)

찾는 값 = 3, 중간값 = 5

1. 찾는 값이 중간 값보다 작으므로 최대값은 4가 된다.

1

2

3

4

5

6

7

8

9

시작값 = 1, 최대값 = 4 찾는값 = 3 중간값 = 2

2. 찾는 값이 중간 값보다 크므로 시작값은 = 3

1

2

3

4

5

6

7

8

9

시작값 = 3, 최대값 = 4 찾는값 = 3 중간값 = 33. 찾는 값과 중간값이 같으므로 3은 정렬된 숫자에 존재합니다.

1

2

3

4

5

6

7

8

9

이 문제에서는 배열의 값이 i×j의 값을 가진다는 것에 규칙을 발견할 수 있습니다.

1	2	3	4	5
2	4	6	8	10
3	6	9	12	15
4	8	12	16	20
5	10	15	20	22

배열이 행을 기준으로 첫 숫자의 배수로 진행됩니다.

첫 번째 행은 1의 배수

두 번째 행은 2의 배수

세 번째 행은 3의 배수

 

또 다른 규칙으로는 예제 입력1에 값들을 오름차순으로 표현하면(파란색 배열 값, 검은색 인덱스)

1	2	2	3	3	4	6	6	9
0	1	2	3	4	5	6	7	8

찾는 값이 7이므로 B[7] = 6이 됩니다. 여기서 보면 찾는 값 7은 해당하는 값의 작거나 같은 수의 값과 동일합니다.

배열에서 인덱스 7은 8번째 값과 동일하며 7의 해당하는 값인 6보다 작거나 같은 수도 8개가 있습니다.

 

배열에 존재할 수 있는 수 범위에서 중간값을 구해서 그 값보다 작거나 같은 수의 개수를 구해서 찾는 인덱스와 비교하여 이분탐색을 진행하면 됩니다.

 

예제입력1에서는 배열에 들어갈 수 있는 숫자의 범위가 1~9로 볼 수 있습니다.

범위를 더 간략하게 보면 k의 해당하는 값은 k보다 클 수 없습니다.

왜냐하면 배열은 배수의 형태로 나타내기 때문에 k이하의 값이 1번 이상은 무조건 나오기 때문입니다.

그래서 범위를 더 간단하게 만들면 1~k로 볼 수 있습니다.

 

여기서 UpperBound를 사용하면 인덱스의 해당하는 값의 동일한 값중에 가장 큰 인덱스를 가져오게 되므로 UnderBound를 구하는 공식을 사용할 것입니다.

UnderBound는 아래 문제에서 Start로 표현하는 것을 참고하시면 감사하겠습니다.

[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)10816번, 숫자 카드 2

 

예제입력 1에서 N=3, K=7일 때 구하는 것을 살펴보도록 하겠습니다.

1~7 범위에서 이분탐색으로 중간값보다 작거나 같은 값들의 개수를 확인하여 k의 인덱스의 값을 얻어내는 것입니다.

 

작거나 같은 개수를 확인할 때에는 배열이 배수의 형태로 나온다는 것을 확인하였으니 배수에서 작거나 같은 값을 얻어내는 방법은

비교 값/배수 첫 번째 수 입니다.

예를 들어 구구단으로 살펴보면

1단은 {1,2,3,4,5,6,7,8,9}

2단은 {2,4,6,8,10,12,14,16,18}

3단은 {3,6,9,12,15,18,21,24,27}

...

9단은 {9,18,27,36,45,54,63,72,81}

해당 값보다 작은 수의 개수는 모두 비교하면서 진행해도 되지만 시간복잡도가 비효율적이기 때문에간단한 수학적 식으로 비교값을 7로 잡으면 7보다 작거나 같은 값은1단 : 7/1 = 7개2단 : 7/2 = 3개3단 : 7/3 = 2개...9단 : 7/9 = 0개위와 같이 간단하게 구하실 수 있습니다.

 

공유기 설치할 수 있는 집들 사이의 최대 값 = 7, 최소 값 = 1

1

~

7

1. 중간값은 (1+7)/2 = 4입니다.

4보다 작거나 같은 배열의 값의 개수를 구해보겠습니다.(N이 3이므로 3의 배수까지 배열에 들어갑니다.)

1	4/1	= 4
2	4/2	= 2
3	4/3	= 1

여기서 배열을 살펴보면 N=3이기 때문에 1단은 {1,2,3}까지의 수밖에 없습니다. 하지만 위에 표에서는 {1,2,3,4}로 볼 수 있어서 이런 상황이 발생하면 안되기 때문에 조건을 하나 설정해야 합니다.

해당 배수의 작거나 같은 값의 개수가 N보다 클 경우 N의 값이 개수가 되어야 합니다.

왜냐하면 배열 크기가 N×N이면 배수마다 개수가 N보다 클 수 없기 때문입니다.

그래서 위에 표를 다시 작성하면(N=3)

1의 배수	4/1	= (4>N) 3
2의 배수	4/2	= 2
3의 배수	4/3	= 1

이제 개수를 살펴보면 6개로 6<K이므로 K의 해당하는 값이 아니다.

개수가 K보다 작기 때문에 중간값보다 더 큰 값에서 작거나 같은 수의 개수를 구해야 해서 범위를 조정해야 합니다.

그래서 범위는 최대 값 = 7, 최소 값 = 5

5

~

7

2. 중간값은 (5+7)/2 = 6입니다.

6보다 작거나 같은 배열의 값의 개수를 구해보겠습니다.(N = 3, 3의 배수까지 배열에 들어갑니다.)

1의 배수	6/1	= (6>N) 3
2의 배수	6/2	= 3
3의 배수	6/3	= 2

이제 개수를 살펴보면 8개로 8>K이므로 동일한 값이 존재할 가능성이 있어서 K의 값이라고 부정할 수는 없지만 다른 값일 수 있으므로 해당 값을 포함하는 범위에서 개수가 있는지 확인해야합니다.

그래서 범위는 최대 값 = 5, 최소 값 = 6

5

~

6

3. 중간값은 (5+6)/2 = 5입니다.

5보다 작거나 같은 배열의 값의 개수를 구해보겠습니다.(N = 3, 3의 배수까지 배열에 들어갑니다.)

1의 배수	5/1	= (5>N) 3
2의 배수	5/2	= 2
3의 배수	5/3	= 1

이제 개수를 살펴보면 6개로 6<K이므로 K의 해당하는 값이 아니다.

개수가 K보다 작기 때문에 중간값보다 더 큰 값에서 작거나 같은 수의 개수를 구해야 해서 범위를 조정해야 합니다.

그래서 범위는 최대 값 = 6, 최소 값 = 6

하지만 UnderBound로 구현하였기 때문에 최대 값와 최소 값이 같아져서 이분 탐색을 마칩니다.

K=7에 개수가 딱 맞는 값은 찾지는 못하였지만 동일한 값이 반복할 수 있다는 점이 있어서 최소 값이 해당 인덱스 값이 됩니다. 그래서 최소 값을 결과로 반환하여 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 범위(1 ~ K)에서 중간값을 구합니다.

2. 중간값보다 작거나 같은 배열의 값 개수를 구합니다.

3. 필요한 개수가 나오면 중간값보다 더 작은 범위로, 나오지 않는다면 큰 범위로 이분탐색을 진행합니다.

4. 위 과정을 반복하여 최소 값이 최대 값과 같아졌을 때 최소 값를 반환합니다.

 

※중간값 구하는 공식 = (시작값 + 최대값) / 2

• BufferedReader를 사용하여 입력 값을 받았습니다.
• K번째 값 찾는/중간값보다 작거나 같은 배열의 값 개수를 구하는 findK,check함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 K번째의 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• findK함수에서 이분탐색에 UnderBound를 사용하여 K번째 수를 구하였습니다.
• check함수에서 중간값보다 작은 배열의 값의 개수를 구하였습니다.
• check함수에서 각 행의 배수의 개수는 N보다 클 수 없기 때문에 Math.min()을 이용하여 조절하였습니다.

 

결과 코드

import java.io.*;
public class Main{
	static int N;	//배열 크기
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 처리하는 BufferedWrtier
        //------입력값 저장-------
        N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        //-------함수 실행 및 결과 출력---------
        bw.write(findK(1, K, K) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    //-------UnderBound 사용한 K번째 찾는 함수-------
    public static int findK(int start, int end, int K) {
    	while(start<end) {
    		int median = (start + end)/2;
    		if(check(median)<K)
    			start = median+1;
    		else
    			end = median;
    	}
    	return start;
    }
    //---------중간값보다 작거나 같은 배열 값의 개수 구하는 함수--------
    public static int check(int median) {
    	int result = 0;
    	for(int i=1;i<=N;i++) 
        /*
        배열의 크기가 N이기 때문에 각 행의 배수의 개수가
        N보다 클 수 없으므로 Math.min()을 이용해서 더 큰 값이 나오면
        N이 더해지도록 하였습니다.
        */
    		result += Math.min(median/i, N);
    	
    	return result;
    }

}