[백준_19637번] IF문 좀 대신 써줘

https://www.acmicpc.net/problem/19637

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 ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105)

 두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 

 N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

 

[코드]

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

class power_19637 {
	String state; // 상태
	int energy; // 전투력
	
	public power_19637(String state, int energy) {
		this.state=state;
		this.energy=energy;
	}
}

public class BaekJoon_19637 {
	static ArrayList<power_19637> arr=new ArrayList<>();
	static int n,m;
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st=new StringTokenizer(br.readLine()," ");

		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		// 각 상태을 측정할 전투력을 입력받아 리스트에 저장
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine()," ");
			String s=st.nextToken();
			int e=Integer.parseInt(st.nextToken());
			
			arr.add(new power_19637(s,e));
		}
		
		// 전투력을 입력받아 어떤 상태인지 출력
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine()," ");
			int e=Integer.parseInt(st.nextToken());
			
			sb.append(binarySearch(e)).append("\n");
		}
		
		System.out.println(sb);
	}
	
	// 이진탐색
	static String binarySearch(int state) {
		int start=0;
		int end=arr.size()-1; 
		
		while(start<=end) {
			int mid=(start+end)/2;
			
			// 전투력이 mid 번째의 전투력보다 작다면 전투력이 낮은 범위에서 재탐색
			if(state<=arr.get(mid).energy)
				end=mid-1;
			
			// 전투력이 mid 번째의 전투력보다 크다면 전투력이 큰 범위에서 재탐색
			else 
				start=mid+1;
		}
		// 정답 return
		return arr.get(end+1).state;
	}
}

 

[고찰]

 이번 문제는 주어지는 칭호와 캐릭터의 개수가 많기 때문에 이진탐색을 사용하는 문제였다. 또한 시간초과를 받지 않기 위해서는 Scanner가 아닌 BufferedReader를 사용해야 하고, 정답을 출력할 때도 StringBuilder를 사용해야 했다. 

 칭호는 입력에 따라 달라지기 때문에 칭호와 전투력 상한가를 같이 저장할 클래스가 필요하고, 이를 연결리스트에 저장하여 이진탐색에 사용해야 한다. 처음에는 이진탐색에 어떤 값을 사용하여 비교해야할지 쉽게 파악하기 여려웠는데 결론은 연결리스트의 인덱스를 사용해야 했다. 이 점만 파악하고 난 후에는 나머지 부분을 쉽게 해결할 수 있었다.