[백준][python] 18870번: 좌표 압축

18870번: 좌표 압축

• 백준(boj) 18870번

문제

수직선 위에 N개의 좌표 $X_1, X_2, …, X_N$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

$X_i$를 좌표 압축한 결과$X’_i$의 값은 $X_i > X_j$를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

$X_1, X_2, …, X_N$에 좌표 압축을 적용한 결과 $X’_1, X’_2, …, X’_N$를 출력해보자.

입력 조건

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 $X_1, X_2, …, X_N$이 주어진다.

출력 조건

첫째 줄에 $X’_1, X’_2, …, X’_N$을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• $-10^9$≤ $X_i$ ≤$10^9$

첫 번째 시도 .

n = int(input())
num = list(map(int,input().split()))

num2 = sorted(num)
result=[]
for i in num:
  result.append(num2.index(i))
print(*result,sep=' ')

»intput

5
2 4 -10 4 -9

»output

2 3 0 3 1

fail(시간 초과)

🌝 Thinking

[아이디어]

1. num을 오름차순으로 정렬하여 num2에 저장한다.
2. num2의 index가 해당값의 순번이 된다.
3. num값이 num2에 몇번째 순번인지 구한다.

.

.

[오류 사항]

1. num값 중 중복된 값을 제거하지 않은 채 num2를 구함으로써 순번이 틀리게 된다.
2. 시간 초과 발생

---

두 번째 시도 .

n = int(input())
num = list(map(int,input().split()))

num2 = sorted(list(set(num)))

hash = {num2[i] : i for i in range(len(num2))}
for i in num:
  print(hash[i],end=' ')

»intput

5
2 4 -10 4 -9

»output

2 3 0 3 1

success

🌝 Thinking

[아이디어]

1. num2에 num에서 중복을 제거하고 오름차순 정렬하여 리스트를 저장한다.
2. 인덱스를 번 째로 계산하지말고, 해당 값을 키(Key), 순번을 값(Value)인 딕셔너리를 만든다.
3. num에서 값(Key)을 꺼내고 순번(Value)를 출력한다.

Hash를 이용하여 시간초과를 해결하였다.

---

💡 깨달은 점.

1. 알고리즘 문제에서 배열에서 .index를 이용하여 원하는 값의 위치값을 뽑는 경우가 많은데 이는 대부분

   dictionary를 이용하면 해결이 된다.