문제

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

Xi를 좌표 압축한 결과 X'i의 값은 Xi > 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

로직

logic

• 입력값 배열에 순위를 매겨주기
• 그러기 위해서는 중복을 제거해주기
• 시간복잡도를 줄이기 위해
• 중복 없는 배열의 값을 key로하고 값으로 순위를 매겨준 map 만들어주기
• map을 활용하면 숫자도 key로 쓸 수 있기 때문에!
• X의 값들을 dict의 key값으로 접근하여 value를 answer배열에 넣어주기
• answer를 한줄로 출력해주기

풀이

{
  const n: string | null = prompt("숫자의 개수를 입력해주세요.");
  const N: number = n ? parseInt(n) : 0;
  if (N >= 1 && N <= 1000000) {
    const numbers: string | null = prompt(
      "숫자들을 빈칸을 사이에 두고 입력해주세요."
    );
    const nums: Array<number> = numbers
      ? numbers.split(" ").map((v) => parseInt(v))
      : [];
    if (nums.length === N) {
      const dict = new Map();
      const numsCopy: Array<number> = [];
      nums.map((v) => (numsCopy.includes(v) ? numsCopy : numsCopy.push(v)));
      numsCopy.sort();
      numsCopy.map((item, idx) => dict.set(item, idx));
      const ans : Array<number> = []
      nums.map((v) => ans.push(dict.get(v)));
      console.log(ans.join(" "))
    } else {
      console.log("입력한 숫자의 개수가 불일치합니다.");
    }
  } else {
    console.log("숫자 N의 개수가 부적절합니다. (1 ≤ N ≤ 1,000,000)");
  }
}

/**
   * test1
   * 
   * input
  5
  2 4 -10 4 -9
   * output
  2 3 0 3 1
   * 
   * test2
  6
  1000 999 1000 999 1000 999
  * output
  1 0 1 0 1 0
  
   */

😂Trial & Error

• for문에서 인덱스로 배열들을 접근하려다 보니까 시간 복잡도가 n²이 되어서 시간초과가 발생...map 자료구조를 활용해서 키로 바로 값에 접근해서 시간복잡도 줄이기!