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

문제 링크

10816번: 숫자 카드 2

---

주의사항

• 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

이 문제에서는 이분 탐색을 조금 응용한 알고리즘을 사용해야 합니다.

 

문제에서는 해당하는 숫자의 개수를 구하는 것으로 해당 숫자에 범위를 구해야하는 문제입니다.

 

그래서 해당하는 숫자가 시작하는 인덱스와 그 숫자가 끝나는 인덱스 + 1을 구해서 범위를 만들어서 몇 개를 가지고 있는지 확인하는 방법입니다.

 

그래서 저는 시작하는 인덱스를 Start, 끝나는 인덱스 + 1은 End로 지정하여 사용하였습니다.

 

간단하게 예를들어 아래에 오름차순으로 정렬된 수들에서 7의 개수를 찾는다고 하면

 

1

2

3

4

5

7(Start)

7

7

9(End)

인덱스 범위는 6~9로 개수는 9 - 6 = 3개가 됩니다.Start와 End를 구하는 과정은 기본 이분 탐색트리에서 살짝 응용만하여 구하였습니다.

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

1. 입력값을 배열에 저장하여 오름차순으로 정렬하였습니다.

2. 범위(시작값 ~ 최대값)에서 중간값을 구합니다.

3. 중간값과 찾는 값을 비교하고 동일하면 1을 출력하고 크거나 작으면 시작값이나 최대값을 조정합니다.

4. 위 과정을 Start 찾는 과정과 End 찾는 과정으로 2번 반복하였습니다.

5. End - Start로 숫자의 개수를 구하였습니다.

 

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

※값을 찾을 때에는 최대값 = 배열.length - 1을 하였지만 여기서는 최대값 = 배열.length로 하였습니다.

 

이유는 length-1로 최대값을 주면 입력값이 오름차순 수에 포함되지 않아도 배열.length-1의 인덱스 값에서 멈추게 될 수 있기 때문입니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 카드의 값과 찾는 값을 나누었습니다.
• for문을 통해서 카드값에 대한 배열을 초기화 후 Arrays.sort로 오름차순 정렬하였습니다.
• Start, End를 구하는 cardStart,cardEnd함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 End-Start = 개수 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cardStart/cardEnd함수에서 이분탐색을 응용하였습니다.
• cardStart함수에서 동일한 숫자거나 큰 숫자일 때 해당하는 숫자도 포함하여 이분 탐색으로 나누었습니다.
• cardEnd함수에서 작은 숫자일 때 해당하는 숫자도 포함하여 이분 탐색으로 나누었습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] card;		//카드 수 저장하는 배열
    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));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화------
        int N = Integer.parseInt(br.readLine());
        card = new int[N]; 
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++) 
        	card[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(card);		//오름차순 정렬
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++) {
        	int num = Integer.parseInt(st.nextToken());
        	int start = cardStart(num);	//Start 구하기
        	int end = cardEnd(num);		//End 구하기
        	if(start == end)		//입력값이 배열에 존재하지 않을 경우
        		bw.write(0 + "\n");
        	else
        		bw.write((end - start) + "\n");	//개수 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //Start 구하는 함수
    public static int cardStart(int n) {
    	int start = 0;
    	int end = card.length;
    	while(start<end) {
    		int median = (start + end)/2;
    		if(card[median]>=n) 
    			end = median;
    		else
    			start = median + 1;
    	}
    	return start;
    }
    //End 구하는 함수
    public static int cardEnd(int n) {
    	int start = 0;
    	int end = card.length;
    	while(start<end) {
    		int median = (start + end)/2;
    		if(card[median]<=n) {
    			start = median + 1;
    		}else
    			end = median;
    	}
    	return start;
    }
}