[Baekjoon] 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

---

첫 번째 시도

사실 문제 자체는 이해하기 어려워서 구글링을 통해 이해했다. 이해하고 나니 풀이는 바로 생각났고 메모리나 시간제한만 신경 쓰면 될 것 같았다.

const input = fs.readFileSync(filePath).toString().trim().split('\n');
const positions = input[1].split(' ').map(Number);
const set = [...new Set(positions)].sort((a, b) => a - b); // 중복 제거 및 정렬
const dictionary = set.reduce((res, curr, idx) => ({...res, [curr]:idx}), {}); // index로 dictionary
const answer = positions.map((v) => dictionary[v]);
console.log(answer.join(' '));

 

dictionary 로 좌표로 index를 찾을때의 시간을 줄이는 것 까지는 맞는 것 같았는데 시간초과가 났다.
또 고민을 해보다가 아무래도 reduce의 문제가 맞는 것 같아서 reduce의 시간복잡도에 대해 찾아보았더니 정답이었다.
정확히는 reduce와 spread syntax (스프레드 연산자) 를 함께쓰는 것이 시간복잡도를 증가 시키는 것.

 

왜 그런걸까?

spread syntax는 내부적으로 Object.asign() 처럼 동작한다. (참고)  => 시간복잡도가 O(N) 
그리고 실행했던 reduce를 살펴보면 배열에 대해 N번 실행 => 시간복잡도 O(N)
그러므로 reduce의  O(N)만큼 O(N)이 수행되는 것이기 때문에 O(N^2)만큼 수행된다고 볼 수 있다.

 

그럼 어떻게 해야할까?

object를 만들어주고 reduce 대신 array 의 forEach로 object[a] = b 실행시켜주면 된다. => 시간복잡도 O(N)

 

두 번째 시도 - 성공!

const input = fs.readFileSync(filePath).toString().trim().split('\n');
const positions = input[1].split(' ').map(Number);
const set = [...new Set(positions)].sort((a, b) => a - b);
let dictionary = {};
set.forEach((v, idx) => (dictionary[v] = idx));
const answer = positions.map((v) => dictionary[v]);
console.log(answer.join(' '));

---

마무리

reduce와 spread syntax를 함께 사용하는 것에 대한 포스트들을 읽다보니 실무에서 사용했었던 경험들이 떠올랐다. 다행이 데이터들이 크지 않아서 체감되는 속도 저하는 없었겠지만 앞으로는 시간복잡도에 대해서도 한번 더 생각해볼 수 있는 기회가 될 것 같다.

 

참고

- https://github.com/tc39/proposal-object-rest-spread/blob/main/Spread.md
- https://donggov.tistory.com/207
- https://prateeksurana.me/blog/why-using-object-spread-with-reduce-bad-idea/

Why using object spread with reduce probably a bad idea

proposal-object-rest-spread/Spread.md at main · tc39/proposal-object-rest-spread

자바스크립트 reduce 사용 시 주의점