정렬. 10단계
18870번. 좌표 압축

문제

18870번 문제 링크

solution

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

const iter = Number(input[0]);

const arr = input[1].split(" ").map((item) => Number(item));

// 중복 제거 및 배열로 타입 변환
let coord = Array.from(new Set(arr));

// coord 배열 원소 오름차순 정렬
coord.sort((a,b) => a - b);

let obj = {};

coord.forEach((item, index) => {
    // key - value로 객체 생성
    obj[item] = index;
})

let ans = [];

arr.forEach((item) => {
    ans.push(obj[item]);
});

console.log(ans.join(" "));

원래 데이터를 담고 있는 arr 배열이 있다.
중복값을 제거하고 오름차순 정렬한 coord 배열이 있다.
coord 배열은 작은 숫자부터 나열되며, 이들의 인덱스는 곧 본인보다 작은 숫자의 개수를 의미한다.
coord 배열을 활용하여, 객체 obj를 생성하고, key - value로 원소값 - index를 넣어준다.
arr 배열의 원소값과 obj 객체의 key가 동일한 의미를 가지고 있으므로, 해당 key의 value를 뽑아내면 문제의 답이 될 값들을 얻을 수 있다.

생성되는 배열과 객체가 여러가지라서 헷갈릴 수 있다.
예시를 통해 살펴보자.

입력 데이터
5
2 4 -10 4 -9

첫 번째 숫자, 5는 반복 횟수로 사용하는데, forEach를 사용했기 때문에 없어도 된다.

배열 arr는 두 번째 줄에 있는 숫자들이 들어간다.
[2, 4, -10, 4, -9]

이들의 중복값을 제거하여 coord 배열을 새로 생성한다.
coord 배열은 다음과 같다.
[2, 4, -10, -9]

이 후, 오름차순 정렬을 실행한다.
[-10, -9, 2, 4]

이렇게 변경된 coord 배열을 활용하여, 객체 obj를 생성한다.
obj의 key는 coord의 배열값이 될 것이고, value는 해당 배열값의 index가 들어간다.
따라서, obj는 아래와 같다.

{
	-10 : 0,
    -9 : 1,
    2 : 2,
    4 : 3,
}

즉, 입력 데이터로 받은 배열에서 -10보다 작은 값은 0개이고, -9보다 작은 값은 1개이고 ...
이런 식의 해석이 가능해진다. 여기까지 오면 왜 중복을 제거했는지 바로 이해가 된다.
중복을 제거하지 않으면 obj에서 4가 하나 더 늘어나, 정보 판단에 방해가 되기 때문이다.

arr 배열의 길이만큼 답을 뽑아내야하기 때문에 coord 배열을 사용하는게 아닌, arr 배열을 사용한다.

arr 배열의 각 값은 obj 객체의 key값으로 쓰이고 있는데, 이를 활용하여 value값에 접근한다.

즉, obj[arr[0]]에 접근하는 것은 obj[2]에 접근하는 것과 같고
이는 obj의 2라는 key값에 접근하여 value를 얻는 것이다.
이런 방식으로 ans 배열에 value 값들을 push해준다.
그 결과, ans 배열은 다음과 같다.

[2, 3, 0, 3, 1]

이를 join(" ")을 활용하여 한번에 문자열로 출력한다.

시간 초과

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

const iter = Number(input[0]);

const arr = input[1].split(" ").map((item) => Number(item));

// 중복 제거 및 배열로 타입 변환
let coord = Array.from(new Set(arr));

// coord 배열 원소 오름차순 정렬
coord.sort((a,b) => a - b);

let ans = [];

arr.forEach((item) => {
    ans.push(coord.indexOf(item));
});

console.log(ans.join(" "));

주의할 점

이번 문제는 시간 초과가 관건이었다.
배열의 indexOf를 사용하게되면 시간 복잡도가 커서, 오답이 된다.
배열이 아닌 객체를 활용하는 방법으로 전환하면 이는 해결된다.
이에 대해서는 이 블로그 글을 보시면 좋을 것 같다.
결과만 말하자면, indexOf의 시간복잡도는 O(n)이며, 객체를 활용하는 방법은 O(1)이기 때문에 시간 초과 문제가 해결된다.

참고 자료

참고 자료 1