[백준] IF문 좀 대신 써줘 : 19637 : JAVA - 이분탐색 (S3)

1. 💎 문제

19637번: IF문 좀 대신 써줘

 

 

 

 

2. 🤔 어떻게 풀까

이 문제는 M개의 전투력에 대해 칭호를 매개주면 되는 문제이다. 하지만 문제는 칭호의 개수와 M의 수가 10^5이라는 것이다. 시간 복잡도가 O(n^2)이하로 풀어야한다. 칭호의 상한선이 오름차순으로 주어지기 때문에 정렬된 상태로 이진 탐색을 쓰기 좋은 상태이므로  빠르게 진행하기 위해 이진 탐색을 이용한다. 

이분 탐색

시간 복잡도 : O(log2N)
범위를 반으로 나누며 탐색 범위를 줄이고 탐색한다. 이때 데이터는 정렬된 상태여야 한다

 

이진 탐색 때 중요한 것은 아래 2개이다. 

 

 ◆ 무엇을 탐색 기준으로 할 것인지

 ◆ low와 high 값 중 어떤 것을 결과로 출력할 것인지

 

무엇을 탐색 기준으로 할 것인지만 잘 정하면 거의 완성이다. 이문제에서는 상한선의 기준이 데이터로 주어지므로 상한선을 담은 배열의 `인덱스`를 기준으로 하였다. 그리고 상한값에 따라 칭호 이름을 저장하기 위해 `HashMap`을 사용한다.

 

 

 

3. 💡 풀이 로직

1.  N개의 칭호 정보 입력 

입력으로 주어지는 `<상한 값, 칭호 이름>`을 `HashMap`으로 입력 받는다. 문제의 조건에서 여러 개의 칭호를 가질 수 있는 경우 먼저 나온 칭호를 출력하라고 했으므로 중복되는 상합 값이 나오면 추가하지 않는다. 해쉬 맵에 추가된 데이터를 상한 값만을 저장해두는 `nums` 배열에 삽입한다.

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		HashMap<Integer, String> titles = new HashMap();
		int [] nums = new int[N];
		int count = 0;
		
		// N개의 칭호 입력 - 해쉬맵, 값 배열
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String title = st.nextToken();
			int num = Integer.parseInt(st.nextToken());
			
			if(titles.containsKey(num))
				continue;
			titles.put(num, title);
			nums[count++] = num;
		}

 

 

2. 전투력에 맞는 칭호 판별

low는 0으로  high는 배열의 사이즈인 count-1로 초기화 한다. low와 high는 인덱스를 가리킬 것이다.

 

`nums[mid] >= power`일 때 즉, 판별해야 되는 전투력이 칭호보다 작을 경우 칭호를 더 낮춰야 하므로 high = mid-1로 변경한다.

 

반대로 `nums[mid] < power`일 때 즉, 판별해야 되는 전투력이 칭호보다 클 경우 칭호를 더 높여야 하므로 low = mid+1로 변경한다. 

그러고 while문을 탈출했을 때에는 판별해야 하는 전투력이 기준이 되는 칭호의 전투력보다 커서 left 값이 +1되거나 판별해야 하는 전투력이 기준이 되는 칭호의 전투력과 같거나 작아서 right값이 -1 되는 것이기 때문에 left 값을 답으로 출력해준다.(둘 중에 무엇을 선택해야하는지 아직 잘 모르겠다..)

	//M개의 전투력에 맞는 칭호 판별
		for(int i=0; i<M; i++) {
			int power = Integer.parseInt(br.readLine());
			// 한 개의 칭호 이진탐색
			int low = 0;
			int high = count-1;
			
			while(low <= high) {
				int mid = (low+high)/2;
				
				// 현재 전투력이 칭호보다 작은 경우
				if(nums[mid] >= power) {
					high = mid -1;
					
				}
				// 현재 전투력이 칭호보다 큰 경우
				else if(nums[mid] < power) {
					low = mid+1;
					
				}
			}
			// 현재 전투력이 칭호보다 큰 경우 
			bw.write(titles.get(nums[low]) + "\n");
		}

 

 

 

 

 

4.  🖥️  전체 코드

import java.util.*;
import java.io.*;

public class Solution {

	public static void main(String[] args) throws Exception{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		HashMap<Integer, String> titles = new HashMap();
		int [] nums = new int[N];
		int count = 0;
		
		// N개의 칭호 입력 - 해쉬맵, 값 배열
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String title = st.nextToken();
			int num = Integer.parseInt(st.nextToken());
			
			if(titles.containsKey(num))
				continue;
			titles.put(num, title);
			nums[count++] = num;
		}
		
		//M개의 전투력에 맞는 칭호 판별
		for(int i=0; i<M; i++) {
			int power = Integer.parseInt(br.readLine());
			// 한 개의 칭호 이진탐색
			int low = 0;
			int high = count-1;
			
			while(low <= high) {
				int mid = (low+high)/2;
				
				// 현재 전투력이 칭호보다 작은 경우
				if(nums[mid] >= power) {
					high = mid -1;
					
				}
				// 현재 전투력이 칭호보다 큰 경우
				else if(nums[mid] < power) {
					low = mid+1;
					
				}
			}
			// 현재 전투력이 칭호보다 큰 경우 
			bw.write(titles.get(nums[low]) + "\n");
		}
		
		
		bw.flush();
		
		bw.close();
		br.close();
		
	}

}