[JS로 푸는 백준] 1620. 나는야 포켓몬 마스터 이다솜

접근법

처음 생각나서 구현한 코드는 주어진 입력값을 배열에 담아서 처리하려고 했더니 시간초과가 나왔다. 백준을 풀다보면 정말 많은 시간초과를 만나게 된다. 반복문은 생각보다 많은 시간적, 공간적 비용을 발생시키기 때문에 for loop 사용을 줄이면서 코드를 짜야할 것 같다.

처음 코드

const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

const [N, M] = input.shift().split(' ').map(v=>+v);
let arr = []; // 포켓몬 도감에 들어있는 포켓몬 이름을 담을 배열
let quiz = []; // 문제를 담을 배열
let answer = '';
for (let i = 0; i < N; i++) {
    arr.push(input[i]);
}

for (let i = N; i <= input.length - 1; i++) {
    quiz.push(Number(input[i]) || String(input[i]));
}

for (let i = 0; i <= quiz.length - 1; i++) {
    if (quiz[i] > 0) {
        answer += arr[quiz[i] - 1] + '\n';
    } else {
        answer += arr.indexOf(quiz[i]) + 1 + '\n';
    }
}
console.log(answer.trim());

해쉬테이블 : Map

해쉬(Hash)란 키(key)와 값(val) 짝을 이루는 dict 형태의 자료구조이다. Hash 함수를 통해 빠른 탐색이 가능하다. 시간복잡도 O(1).

Javascript에서는 기본적으로 해쉬테이블을 만들 수 있도록 ES6부터 Map을 지원해주고 있는데, 이를 사용하면 여러가지 메서드를 사용해서 해쉬테이블을 조작할 수 있다.

1. set(key, val)

   key,val 순으로 저장한다. key에는 Number, String, function, object, NaN의 자료형이 들어갈 수 있다.

2. get(key)

   val 값을 얻을 수 있다.

3. has(key)

   val 값을 찾을 수 있다.

4. delete()
   key나 val 값을 삭제할 수 있다.

5. size(key)
   val 값의 존재 유뮤를 확인 할 수 있다.

풀이과정

해쉬맵으로 풀면 쉽게 풀 수 있는 문제였다.하나의 맵만 생성하면 탐색하는 과정에서 시간초과가 또 발생할 수 있지만 Map을 2개 만들면 시간초과가 나지 않는다!

const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input.shift().split(' ').map(v=>+v);
const NumToName = new Map(); // 포켓몬 번호 => 포켓몬 이름
const NameToNum = new Map(); // 포켓몬 이름 => 포켓몬 번호
for (let i = 0; i < N; i++) { // N까지
    NumToName.set(i+1, input[i]); // 1 => 'Bulbasqur' , 2 => 'Ivysaur', ... 26 => 'Raichu'
    NameToNum.set(input[i], i+1); // 'Bulbasaur' => 1, 'Ivysaur' => 2, ... 'Raichu' => 26
}
const quiz = input.slice(N, input.length); // input에서 quiz 뽑아내고
let answer = ''; // 정답 담을 변수 선언
quiz.forEach(v=> {
    if (isNaN(v)) { // 만약 quiz의 요소가 숫자가 아니면?
        answer += NameToNum.get(v) + '\n'; // Ex) NametoNum.get(v='Raichu') => 26 출력
    } else { // 만약 quiz의 요소가 숫자라면?
        answer += NumToName.get(+v) + '\n'; // Ex) NumtoName.get(v=>25) => Pikachu 출력
    }
});
console.log(answer.trim());