[Python] 백준알고리즘 #18870

📝 문제

수직선 위에 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

⌨️ 예제 입력 1

5
2 4 -10 4 -9

🖨 예제 출력 1

2 3 0 3 1

⌨️ 예제 입력 2

6
1000 999 1000 999 1000 999

🖨 예제 출력 2

1 0 1 0 1 0

📚 내가 제출한 코드

import sys
n = int(sys.stdin.readline())
xArr = list(map(int, sys.stdin.readline().split()))
xSet = sorted(list(set(xArr)))
xDict = {xSet[i] : i for i in range(len(xSet))}
for x in xArr:
    print(xDict[x], end = ' ')

✏️ 내가 제출한 코드에 대한 설명

• Dictionary를 써서 key로 값을 검색하는 방식을 사용하면 시간 복잡도가 O(1)로 나오기 때문에 시간 초과가 발생하지 않는다.
• sys.stdin.readline() : 키보드로 입력한 값을 받는 함수 (기존의 input() 보다 속도가 훨씬 빠르다.)
• a.split() : a를 빈칸 단위로 쪼개서 반환하는 함수
• map(a, b) : b의 원소 하나하나를 a에 대입한 것을 반환하는 함수
• set(a) : 리스트의 중복을 없애주기 위해 사용하는데, Type이 list형이 아니라 set형이기 때문에 주의가 필요하다.
• sorted(a) : a를 오름차순으로 정렬해서 반환하는 함수 (≠ a.sort())
• len(a) : 리스트 a의 크기 (요소 개수)
• range(a) : 0부터 a-1까지의 정수를 반환하는 함수
• print(a, end = b) : a를 출력하면서 끝에 b도 붙여서 출력한다.
• 메모리 : 144088 KB
• 시간 : 1884 ms
• 코드 길이 : 217 B

📎 참고

xDict = {xSet[i] : i for i in range(len(xSet))}

for i in range(len(xSet)):
    xDict[xSet[i]] = i

xDict = {x : i for i, x in enumerate(xSet)}

• 이 3가지 코드 모두 가능하다.
• 첫번째 코드 썼을 때 : 1884 ms
• 두번째 코드 썼을 때 : 1980 ms
• 세번째 코드 썼을 때 : 2020 ms

🥲 실패한 코드

import sys
n = int(sys.stdin.readline())
xArr = list(map(int, sys.stdin.readline().split()))
xSet = sorted(list(set(xArr)))
ranks = [i for i in range(len(xSet))]; result = []
for x in xArr:
    index = xSet.index(x)
    result.append(ranks[index])
print(*result)

• 시간 초과가 떠서 그 이유를 검색해보니 내가 쓴 index()의 시간 복잡도가 O(N)임을 알게 되었다. 즉, 최악의 경우에 매번 1000000번씩 실행될 수 있다는 뜻이다.