문제

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

풀이

문제 조건상 숫자가 작을수록 작은숫자이므로 정렬을 해야하고,
중복되는 숫자는 똑같은 값을 가져야 하므로 Set 자료형을 적용해야한다.
정렬된 리스트에서 index를 뽑아쓰면 매 동작마다 O(n)의 시간 복잡도를 가지게 되므로
O(1)으로 값을 참조할 수 있는 해쉬테이블을 이용했다.

요약) 정렬된 중복되지 않은 숫자들을 해쉬테이블에 key : 숫자, value : index로 저장한후 정렬되지 않은 리스트를 value로 바꿔준다.

JavaScript

const numbers = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")[1].split(" ").map(Number);

const sortedNumbers = [...new Set(numbers)].sort((a, b) => a - b);

const hashTable = new Map();
sortedNumbers.forEach((e, i) => hashTable.set(e, i));

const answer = numbers.map((e) => hashTable.get(e));
console.log(answer.join(" "));

Python

input = __import__('sys').stdin.readline
N = input()
numbers = list(map(int, input().split()))

SortedNumbers = sorted(set(numbers))
hashtable = {e : i for i, e in enumerate(SortedNumbers)}

print(' '.join(map(lambda x : str(hashtable[x]), numbers)))