[Baekjoon] 19637_IF문 좀 대신 써줘

Silver III

문제(출처: https://www.acmicpc.net/problem/19637)

---

< IF문 좀 대신 써줘 >

 

문제 풀이 

 

이분탐색을 사용하여 문제를 해결했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _19637_ { // IF문 좀 대신 써줘
	static String name[];
	static int value[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		name = new String[n];
		value = new int[n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());

			name[i] = st.nextToken();
			value[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < m; i++) {
			int num = Integer.parseInt(bf.readLine());
			int result = search(num, 0, n - 1);
			bw.write(name[result] + "\n");
		}
		bw.flush();
	}

	private static int search(int num, int start, int end) {
		if (start > end) {
			return -1;
		}

		int mid = (start + end) / 2;

		if (value[mid] < num) {
			if (value[mid + 1] >= num) {
				return mid + 1;
			}
			return search(num, mid + 1, end);
		} else if (value[mid] >= num) {
			if (mid == 0) {
				return 0;
			}
			if (value[mid - 1] < num) {
				return mid;
			}
			return search(num, start, mid - 1);
		}
		return -1;
	}
}

변수)
n, m : 칭호의 개수, 캐릭터들의 개수
name, value : 칭호의 이름, 칭호의 전투력
num : 캐릭터의 전투력
result : 전투력에 맞는 칭호의 인덱스

 

칭호의 개수와 칭호를 출력해야 하는 캐릭터들의 개수를 입력받는다.

n개의 줄에 칭호의 이름과 칭호의 전투력을 입력받아 각 배열에 값을 저장한다.

m개의 줄에 캐릭터의 전투력을 입력받아 search 함수를 호출한 후 얻은 전투력에 맞는 칭호의 인덱스를 사용하여 칭호를 출력한다.

 

search (캐릭터의 전투력, start, end )

start 값이 end 값보다 크면 조건에 맞지 않으므로 종료

중간 인덱스 값을 start와 end를 합하여 2로 나눈 값으로 구한다.

 

중앙값 < 캐릭터의 전투력인 경우

: 중앙값과 다음 값 구간에 해당하는 값이라면 중앙값+1 인덱스 반환

: 중앙값을 기준으로 오른쪽 데이터셋을 선택한다.

 

중앙값 >= 캐릭터의 전투력인 경우

: 중앙값이 0이라면 0 인덱스 반환

: 중앙값과 그전 값 구간에 해당하는 값이라면 중앙값 인덱스 반환

: 중앙값을 기준으로 왼쪽 데이터셋을 선택한다.

 

모든 경우에 해당하지 않는다면 종료

---

사실 이 문제는 이렇게 해결하는 것이 맞는지 모르겠다! 🫣

 

---