[바미] 나는야 포켓몬 마스터 이다솜

문제

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

코드 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const numToName = new Map();
const nameToNum = new Map();

for (let i = 1; i <= N; i++) {
    const name = input[i];
    numToName.set(i, name);
    nameToNum.set(name, i);
}

let result = [];
for (let i = N + 1; i <= N + M; i++) {
    const query = input[i];
    if (!isNaN(query)) {
        result.push(numToName.get(parseInt(query, 10)));
    } else {
        result.push(nameToNum.get(query));
    }
}

console.log(result.join('\n'));

코드 설명

const [N, M] = input[0].split(' ').map(Number);

먼저 첫 번째 요소를 N, 두 번째 요소를 M에 각각 할당합니다. N은 도감에 수록된 포켓몬의 개수, M은 맞춰야 하는 문제의 개수를 의미합니다.

 

const numToName = new Map();
const nameToNum = new Map();

numToName은 포켓몬 번호를 키로 하여 이름을 값으로 가지는 Map 객체이고,

nameToNum은 포켓몬 이름을 키로 하여 번호를 값으로 가지는 Map 객체입니다.

 

for (let i = 1; i <= N; i++) {
    const name = input[i];
    numToName.set(i, name);
    nameToNum.set(name, i);
}

여기에서 1부터 N까지 반복하여 각 포켓몬 정보를 처리하게 됩니다.

name 변수에서 input 배열에서 각 포켓몬의 이름을 가져오게 되고, 포켓몬 번호 i를 키로, name을 값으로 numToName에 저장하고, 포켓몬 이름 name을 키로, i를 값으로 nameToNum에 저장하게 됩니다.

 

let result = [];
for (let i = N + 1; i <= N + M; i++) {
    const query = input[i];
    if (!isNaN(query)) {
        result.push(numToName.get(parseInt(query, 10)));
    } else {
        result.push(nameToNum.get(query));
    }
}

이제 결과를 저장할 배열을 초기화 해준 뒤,  N+1 번째 줄부터 M개의 문제에 대해 반복 해줍니다.

 

반복문 안에서 처리되는 형태는 먼저 각 문제를 query 변수에 저장해줍니다.

그 후  query가 숫자인지 확인해주는데 숫자일 경우 numToName.get(parseInt(query, 10))을 통해 해당 번호에 해당하는 포켓몬의 이름을 결과 배열에 추가하고,  그렇지 않을 경우 nameToNum.get(query)을 통해 해당 이름에 해당하는 포켓몬 번호를 결과 배열에 추가해줍니다.

 

console.log(result.join('\n'));

그 후 결과 배열을 한 줄씩 출력해줍니다.

문제 풀이

이 문제는 주어진 포켓몬 도감을 이용해 번호 또는 이름을 기반으로 포켓몬 정보를 찾는 문제입니다. 

이를 효율적으로 해결하기 위해 해시맵을 사용하여 해결했습니다.

 

제가 사용한 해시맵은 아래와 같습니다.

• 각 포켓몬 번호를 키로하고, 이것에 해당하는 이름을 값으로 하는 해시맵(번호-이름 매핑)
• 각 포켓몬 이름을 키로 하고, 그에 해당하는 번호를 값으로 하는 해시맵(이름-번호 매핑)

제가 해시맵을 사용한 이유는 입력의 데이터 양이 많고, 빠른 검색을 하기 위해서였습니다.

(해시맵은 0(1)의 시간 복잡도를 갖기 때문이죠.)

 

시간 복잡도

포켓몬 도감에 N개의 포켓몬을 해시맵에 저장하므로 O(N) 시간이 소요됩니다.

그리고 M개의 문제를 각각 해결하는데 각 문제에 대해 O(1) 시간이 소요되므로, 총 O(M) 시간이 소요됩니다.

 

따라서 전체적인 시간 복잡도는 O(N + M)이 됩니다.

공간 복잡도

각각의 해시맵에 N개의 포켓몬을 저장하므로 O(N)의 공간이 필요합니다. 

따라서 전체적인 공간 복잡도는 O(N)이 됩니다.