문제
게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.
예를 들어, 전투력 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 ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105)
두 번째 줄부터 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 5
B 100
A 100
C 1000
99
100
101
500
1000예제 출력 2
B
B
C
C
C문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ19637 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
StringBuilder sb=new StringBuilder();
int N=Integer.parseInt(st.nextToken());
int M=Integer.parseInt(st.nextToken());
String[][] title=new String[N][2];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
title[i][0]=st.nextToken();
title[i][1]=st.nextToken();
}
for(int i=0;i<M;i++){
int num=Integer.parseInt(br.readLine());
int left=0;
int right=N-1;
int mid=(left+right)/2;
while(left<=right){
mid=(left+right)/2;
int titleInt=Integer.parseInt(title[mid][1]);
if(titleInt<num){
left=mid+1;
}
else{
right=mid-1;
}
}
sb.append(title[left][0]+"\n");
}
System.out.print(sb);
}
}단순히 if문을 통해 칭호를 정할 수 있는 문제를 이분탐색을 이용하여 시간복잡도를 줄이는 문제이다.
이때 이분탐색을 진행할 때 필요한 기준은 칭호를 위해 필요한 전투력으로 한다.
칭호 정보 저장하기
String[][] title=new String[N][2];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
title[i][0]=st.nextToken();
title[i][1]=st.nextToken();
}칭호의 이름과 기준이 되는 전투력값을 받아 title 배열에 저장해두고 이분탐색 시 활용한다.
이분탐색
for(int i=0;i<M;i++){
int num=Integer.parseInt(br.readLine());
int left=0;
int right=N-1;
int mid=(left+right)/2;
while(left<=right){
mid=(left+right)/2;
int titleInt=Integer.parseInt(title[mid][1]);
if(titleInt<num){
left=mid+1;
}
else{
right=mid-1;
}
}
sb.append(title[left][0]+"\n");
}left, right는 칭호를 넣은 배열의 인덱스 값으로 설정하여
원하는 값에 도달한 경우 해당 배열의 칭호를 출력하는 방식으로 한다.
칭호를 선정하는데에는 power <= 10000 와 같은 형식이기 때문에 if문으로 묶을때에도 해당 전투력보다 작거나 같은 경우와 전투력보다 큰 경우로 나눠준다.
그러고 while문을 탈출했을 때에는 탐색하고자 하는 전투력이 기준이 되는 칭호의 전투력보다 커서 left 값이 +1되거나
탐색하고자 하는 전투력이 기준이 되는 칭호의 전투력과 같거나 작아서 right값이 -1 되는 것이기 때문에
left 값을 답으로 출력해준다.
시간초과를 없애는 방법
StringBuilder sb=new StringBuilder();
...
sb.append(title[left][0]+"\n");
...
System.out.print(sb);각 캐릭터마다 칭호를 System.out.println() 을 하여 출력하면 시간초과가 발생한다.
이때, Stringbuilder를 이용하여 출력 속도를 줄여 시간초과를 예방한다.
항상 이분탐색을 하게 될 때 어떤 값을 기준으로 해야할지 고민을 한다. 여러 문제를 풀어본 결과 인덱스를 기준으로 탐색을 하거나 주어진 값들을 이용하여 탐색하거나 0에서부터 해당 값까지의 숫자를 기준으로 탐색을 하는 경우가 나오는 것 같다.
이번 문제에서는 이분탐색을 하기 위한 기준을 찾는데에도 시간이 걸렸지만 마지막에 시간초과가 발생하는 바람에 시간이 꽤 걸렸다.
StringBuilder를 까먹고 있다가 시간초과가 발생하여 구글링해보다가 파이썬에서 발생한 시간초과를 sys.stdin.readline 이용하여 해결해보라는 글에 힌트를 얻어 StringBuilder를 이용하여 문제를 해결했다.
