문제

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 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개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

예제 입력

3 8
WEAK 10000
NORMAL 100000
STRONG 1000000
0
9999
10000
10001
50000
100000
500000
1000000

예제 출력

WEAK
WEAK
WEAK
NORMAL
NORMAL
NORMAL
STRONG
STRONG

내가 했던 풀이 방법

1. 칭호를 저장할 title 배열을 초기화해주고, 저장된 칭호의 상한선을 저장할 usedLimit set을 선언해준다.
2. 칭호 상한선이 usedLimit에 존재하지 않는다면 title의 칭호 이름과 상한선을 저장해주고, 상한선을 usedLimit에 추가해준다.
3. M개의 전투력을 이분탐색으로 탐색한다. 처음 left는 0이고 right는 title.length-1이다. 중복된 상한선은 title에 포함되어 있지 않으므로 right는 N-1로 할 수 없다.
4. left가 right와 같거나 작은 동안 mid 값을 이용해 전투력을 비교해준다. 현재 전투력이 mid 전투력의 상한선과 같거나 작다면 current에 칭호를 저장해준다. 전투력이 상한선과 같지 않고 작을 때에도 포함을 해주어야 하는데 해당 칭호보다 더 작은 상한선에도 포함될 경우에 칭호가 2개가 되어버리기 때문에 current를 별도로 관리해주어야 한다.
5. 모든 이분탐색이 끝난 뒤에 current의 칭호를 answer에 더해준다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let [N, M] = n.trim().split(' ').map(Number);

let title = [];
let usedLimit = new Set();
let index = 0;
for (let i = 0; i < N; i++) {
  let [name, limit] = input[index++].trim().split(' ');
  limit = Number(limit);
  if (!usedLimit.has(limit)) {
    title.push([name, limit]);
    usedLimit.add(limit);
  }
}

let answer = '';

for (let i = 0; i < M; i++) {
  let power = Number(input[index++]);
  let current = '';

  let left = 0;
  let right = title.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (power <= title[mid][1]) {
      current = title[mid][0];
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  answer += current + '\n';
}

console.log(answer.trim());

회고

이분탐색은 왜이리 문제만 보고 이분탐색으로 풀어야한다는 걸 인지할 수가 없지..?