[백준] 18870번(좌표 압축)

백준 18870번

처음 제출한 코드(시간초과)

import sys

input = sys.stdin.readline
number = int(input())

lists = list(map(int, input().split()))

lists_copy = lists[:]
lists_copy = set(lists_copy)
lists_copy = list(lists_copy)
lists_copy.sort()

for i in range(number):
  print(lists_copy.index(lists[i]), end=' ')

• 시간초과

• 다른 정답 코드와 비교했을 때 다른 점은 마지막에 압축값을 출력할 때 list.index() 메소드를 사용했다는 것 뿐!
• 대부분의 정답 코드는 값을 출력할 때 dict을 활용

• list.index()의 시간복잡도: O(n)
• dict[index]의 시간복잡도: O(1)
  출처

최종 제출 코드

import sys

input = sys.stdin.readline
number = int(input())

lists = list(map(int, input().split()))

lists_copy = lists[:]
lists_copy = list(set(lists_copy))
lists_copy.sort()

dic=dict()

for i in range(len(lists_copy)):
  dic[lists_copy[i]]=i

for i in lists:
  print(dic[i], end=' ')

• lists_copy[i]: i번째 인덱스에 저장된 값
• dic[lists_copy[i]]=i: 저장된 값에 순서를 매칭하여 저장