오늘은 백준 19637 - IF문 좀 대신 써줘를 풀었다.
문제
게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.
예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.
if power <= 10000
print WEAK
else if power <= 100000
print NORMAL
else if power <= 1000000
print STRONG혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.
입력
첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 10^5)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 10^5)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 10^5)
두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다.
N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.
출력
M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.
예제
입력 1
3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000출력 1
WEAK
WEAK
WEAK
NORMAL
NORMAL
NORMAL
STRONG
STRONG입력 2
3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000출력 2
B
B
C
C
C풀이 방법
나는 사실 이분탐색 분류인 것을 보고 문제 풀이를 시작했다. 하지만 N과 M의 입력 범위가 (1 ≤ N, M ≤ 10^5)인 것을 보면 어느 정도 그냥 탐색으로 풀면 시간초과가 뜰 것이라는 감이 잡힌다. 그러면 효과적인 탐색 방법을 고민하게 되고, 이 문제는 각 범위 중 포함되는 범위 하나를 찾는 것이고, 각 범위가 순서대로 주어지기 때문에 이분탐색을 적용할 수 있는 문제라는 감을 잡을 수 있을 것이다.
위에서 말했듯 내가 찾는 것은 주어진 값이 속하는 범위이다. 그러므로 각 범위들의 기준 값을 배열에 넣어주고, 배열의 인덱스로 이분 탐색을 수행하였다. 아래와 같이 가장 작은 범위를 다른 범위와 일관성 있게 다루기 위해서 전투력이 될 수 있는 범위의 최소값인 0보다 작은 값을 기준 배열의 첫 원소로 같이 넣어주었다.
power <= 가장 작은 기준값같은 기준값이 입력될 수 있다는 조건이 있는데, 나는 입력에서 이걸 걸러주지 않았기 때문에 같은 범위가 있다면 가장 앞에 있는 범위를 찾아야하므로 아래와 같이 left, right 갱신 기준을 설정하였다.
if(threshold[mid] >= power) right = mid;또한 구하는 것이 범위이므로 left와 right의 차가 1이면 범위를 구한 것이므로 탐색을 종료하였고, 출력해야 하는 값은 범위의 상한 기준 값이므로 right를 반환해주었다. 이 때, 범위 기준값이 같을 수 있고, 그래서 그런 경우 가장 앞의 범위를 찾도록 구현했다고 위에 말했지만 그 범위의 하한기준값과 상한기준값이 같을 수 있으므로 이런 경우는 가장 앞의 이름을 반환하기 위해서 left를 반환하도록 조건을 걸어주었다.
나는 이분 탐색 문제가 너무 재밌다 ! 이번 문제도 너무 재밌게 풀긴 했는데 설명을 왜 이렇게 못 하게찌.. 설명이 맘에 안든다. 내가 나중에 읽어도 이해 못 할 거 같아 ㅠㅠ 코드가 더 직관적인 것 같다. 설명이 이해가 안 가면 코드를 봐주시면 될 거 같아요 !
코드
import java.io.*;
import java.util.*;
public class Main {
static class Solution{
private int[] thresholds;
private int left, right, mid;
Solution(int[] thresholds){
this.thresholds = thresholds;
}
int solution(int power){
left = 0;
right = thresholds.length-1;
mid = right;
while(right-left > 1){
mid = (right+left)/2;
if(thresholds[mid] >= power) right = mid;
else left = mid;
}
if(thresholds[left] == thresholds[right]) return left;
return right;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
StringTokenizer st; // tokenizer
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
String[] names = new String[n+1];
int[] thresholds = new int[n+1];
thresholds[0] = -1;
for(int i=1; i<=n; i++){
st = new StringTokenizer(br.readLine());
names[i] = st.nextToken();
thresholds[i] = Integer.parseInt(st.nextToken());
}
Solution solution = new Solution(thresholds);
for(int i=0; i<m; i++){
bw.write(names[solution.solution(Integer.parseInt(br.readLine()))] + "\n");
}
bw.flush(); // flush
bw.close(); // close
br.close(); // close
}
}