백준, 18870 좌표 압축 javascript

백준, 18870 좌표 압축

📖 https://www.acmicpc.net/problem/18870

👨‍💻 문제 풀이

• 시간초과가 중요한 문제
• 아무생각없이 for문으로 반복돌리면 답은 아주 쉽게 나온다.
• 시간초과를 방지하기 위해 map, set 구조를 사용해야만 한다.
• 사실 나를 제외한 나보다 작은 숫자라는건, 정렬된 배열의 Index값과 똑같다.
• 더불어, set을 사용해서 중복을 제거했고, 그를 map에 담아 키, 쌍으로 불러오도록 코드를 작성했다.

💻 제출한 코드

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

const N = +input.shift();

const setArr = input[0].split(' ').map(Number).sort((a,b)=>a-b);
const set = new Set(setArr);
const map = new Map();

[...set].forEach((item, index) => {
    map.set(item, index);
})

let answer = '';
input[0].split(' ').forEach((item, index) => {
   answer += map.get(+item) + ' ';
})

console.log(answer);

이번 문제를 풀면서,

• set을 이용해 중복을 제거하는 부분은 필요없었을 것 같다.
• 이번 문제는 쉽다고 생각했지만 못풀고 있었던... 묵혀뒀던 문제였는데
• 오늘 풀어보니 생각보다는 간단하게 풀려서 기분 좋았다.
• 더불어 시간복잡도를 줄이는 로직에 대해서 더 고민해 봐야할 필요가 있다.