백준 JS | 좌표 압축

1. index 값을 찾기 위해 입력값 내림차순 정렬 배열 만들기 (input 배열과 별도인 arr 배열)

2. 내림차순 정렬된 배열로 index 배열 만들기 ( lineUp 배열 )

3. 입력값 배열의 값을 index 배열의 index 값으로 바꾸기 ( arr 배열의 값을 lineUp 배열의 값과 비교한 후 그 index 값으로 교체)

4. index 로 교체된 입력값 배열 출력하기 ( index 값으로 교체된 arr 배열을 출력하기)

❌ Solution (시간초과)

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n')
input.shift();
let answer = '';
//1. 좌표 배열 정렬하기
const arr = input[0].split(' ').map(el => parseInt(el));

//2. index 값 찾기 위한 lineUp 배열 만들기
const setArr = new Set(arr)
const lineUp = [...setArr].sort((a,b) => a-b);

//3. lineUp 배열로 index 값 찾아서 좌표배열와 매칭
arr.forEach(el => answer += lineUp.indexOf(el) + ' ');
console.log(answer);

코드에는 문제 없어 보이고 입력값을 사용하여 RunJS에서 코드를 돌려보아도 답은 맞는데, 시간 초과로 오답체크가 되는 것으로 봐서 Set, 혹은 indexOf 메소드를 사용하여 시간이 초과되는 것으로 의심되었다.

구글링을 통해 Set을 사용하고도 정답으로 처리된 답안들이 존재하는 것으로 보아 consle.log 가 여러번 출력되면 시간초과 에러가 발생했던 경우와 유사하게 indexOf 메소드를 사용하는데 시간이 많이 소요되는 것으로 의심이 되었고 이를 대체하기 위한 방법으로 hashMap을 사용 해보았다.

✅ Solution

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n')
input.shift();
let answer = '';
//1. 좌표 배열 정렬하기
const arr = input[0].split(' ').map(el => parseInt(el));

//2. index 값 찾기 위한 lineUp 배열 만들기
const setArr = new Set(arr)
const lineUp = [...setArr].sort((a,b) => a-b);

//3. idx 찾기 위한 hashMap 생성
const hashMap = {};
lineUp.forEach((el,idx) => hashMap[el] = idx);

//4. hashMap 활용하여 arr의 idx 값 활용하여 answer string 만들기
arr.forEach(el => answer += hashMap[el] + ' ');
console.log(answer)

indexOf의 시간복잡도와 hash 의 시간복잡도에 대해서 알고 사용한 것은 아니고 어렴풋이 참고자료에 있던 2 영상을 본 기억을 더듬어서

hash를 사용하면 더 빠르지 않을까 라는 막연한 생각에 시도해보았는데 운 좋게 이 방법을 통해 해결할 수 있었다.

문제를 해결하고 다시 영상을 찾아보니 Hash Map과 Hash Table 2가지가 엄연히 다르며 내가 본 것은 Hash Map이 아니라 Hash Table에 관한 영상이었다.

 

모든 것을 알 필요는 없지만 문제가 발생했을 때 해당 문제를 해결하기 위해 어떤 방법들을 찾아봐야할지 정확한 구글링을 하기 위해서 얇고 넓은 지식과 꾸준한 학습의 필요성에 대해 느낄 수 있었던 경험이었다. 

다음에는 Hash Map과 Hash Table에 대해서 포스팅을 작성해보아야겠다.

💡 참고자료
포프TV - Hash Table은 프로그래머의 기본기
노마드 코더 Nomad Coders(유튜브) - 개발자라면 꼭 알아야할 Hash Table 의 모든 것!