백준 좌표압축 18870 js

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

18870번: 좌표 압축

 

로직

정렬해서 작은 숫자 인덱스 번호 순으로 출력해주면 된다.

 

예)

5
2 4 -10 4 -9

 

출력)

 

-10 - 9 2 4 4

 

-> 순서 0 1 2 3 3

출력에 맞게 순서 조정

 

정답 - > 2 3 0 3 1

 

 

내 틀린 코드 1

function solution(arr) {
  let answer = [];

  let left = 0;
  let right = 1;
  let count = 0;

  let sem = 0;

  while (left !== arr.length) {
    if (right === arr.length) {
      sem = 0;
      right = 0;
      left++;
      answer.push(count);
      count = 0;
    }

    if (sem !== arr[right] && arr[left] > arr[right]) {
      // 1000 > 999
      //   rigth
      sem = arr[right];
      count += 1;
      //   console.log(arr[left], arr[right], count, "\n");
    }

    right++;
  }
  console.log(answer.join(" "));
}

solution(arr);

left rigth 투포인트 방식으로

sem 이라는 변수에 중복이 될만한 값을 저장해서 걸러내고 right 를 계속 증가시키고

배열의 마지막 부분에 도달했을 때 left ++ right = 0 으로 다시 다음 숫자를 순회해줬다.

 

입력갯수 100만에 시간이 2초라는 걸보고 속도가 중요하다는 생각이 들어서 2중 for 문을 안돌리려고

while() 을 사용했는데 결국은 2중 for문이 돌아간것과 비슷한 코드가 됬다.

 

-> 시간초과

 

2번째 틀린코드

const filter = arr.filter((v, i) => arr.indexOf(v) === i).sort((a, b) => a - b);

let sum = [];
arr.forEach((e) => {
  let index = filter.findIndex((v) => e === v);

  sum.push(index);
});
console.log(sum.join(" "));

여전히 인덱스로 접근을 했고

filter 내장함수와 IndexOf 로 중복을 제거하고 바로 sort로 정렬해주었다.

 

원본 배열에서 중복을 제거하고 정렬을 해주었던 filter 에서 인덱스 값을 찾아서 sum 배열에 푸쉬하여 꺼내줬다.

 

요것도 시간 초과

 

틀린코드 3 (정답 흡사 코드)

const filter = arr.filter((v, i) => arr.indexOf(v) === i).sort((a, b) => a - b);

let obj = {};

for (let k in filter) {
  obj[filter[k]] = k;
}

let sum = "";
for (let i = 0; i < arr.length; i++) {
  sum += obj[arr[i]] + " ";
}

console.log(sum);

이게 나중에 정답코드가 되는 코드인데

객체의 key value 로 인덱스 번호를 저장해서 하나씩 꺼내는 방식인데

투포인트 할때 많이 했었던 것 같다.

 

결론은 이것도 시간초과로 틀린코드

 

 

정답코드

 

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./준/정렬/18870/input.txt";

const input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = input.shift();
const arr = input.shift().split(" ").map(Number);

let set = new Set(arr);
let filter = [...set].sort((a, b) => a - b);

let obj = {};

for (let k in filter) {
  obj[filter[k]] = k;
}

let sum = "";
for (let i = 0; i < arr.length; i++) {
  sum += obj[arr[i]] + " ";
}

console.log(sum);

 

 

이건 정답코드인데

틀린코드 3 과 다 똑같은데 다른 점이 1~2줄 있다.

바로 중복제거 하는 방법인데

바로 위의 코드는 fitler 내장 함수에서 indexOf 로 해주었고 정답코드에서는 new Set() 을 해주었다.

---

푸념..

정렬부분에서 sort 부분도 그러고 중복제거 set 부분도 그러고

 

물론 내장함수가 간단하고 편하고 빠르고 좋고 내장함수를 똑같이 구현해보라고하면 못하겠지만

 

버블, 삽입, 병합, 퀵 등등 정렬알고리즘을 연습하고자 문제를 풀었는데

 

내장함수에 치중되면서 이게 sort 한두번에 해결 되는 문제면 문제 푸는 의미가 있는가 싶은 현탐도 잠깐씩 오는 것 같다.